The Role of Regular Integers Modulo n in RSA Cryptography

Klaus Dohmen; Mandy Lange-Geisler

Paper 2026/1589

The Role of Regular Integers Modulo n in RSA Cryptography

Klaus Dohmen

, Hochschule Mittweida

Mandy Lange-Geisler

, Hochschule Mittweida

Abstract

We investigate a multi-prime multi-power generalization of the RSA cryptosystem for arbitrary moduli $n>1$, which under reasonable cryptographic assumptions works correctly for almost all messages $m<n$. Based on a new sharpening of Carmichael's theorem, tailored to regular integers modulo $n$, we prove that this generalization is correct precisely for messages represented by regular integers modulo $n$, thereby generalizing the original RSA correctness theorem. As in the original RSA scheme, decryption can be accelerated by Chinese remaindering, yielding a corresponding generalization of CRT-RSA.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: RSA CRT-RSA multi-prime multi-power regular integer modulo n lambda function Carmichael's theorem
Contact author(s): dohmen @ hs-mittweida de
mlange1 @ hs-mittweida de
History: 2026-08-06: approved; 2026-08-03: received; See all versions
Short URL: https://ia.cr/2026/1589
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1589,
      author = {Klaus Dohmen and Mandy Lange-Geisler},
      title = {The Role of Regular Integers Modulo n in {RSA} Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1589},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1589}
}