On the Existence of Multiple RSA Private Keys

It is known that, given an RSA modulus, , the public key and the corresponding private key satisfy the modulo congruence , where . Usually, the private key can be computed efficiently using the extended Euclidean algorithm, and it is common knowledge that the private key is unique in the sense of modular . This paper shows that there exist multiple private keys ; they all satisfy that . This paper also presents the exact relationship between an RSA public key and a corresponding private key.