Paper 2026/1589 Original: eprint.iacr.org/2026/1589 ↗

The Role of Regular Integers Modulo n in RSA Cryptography

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.