Generating RSA keys without the Euclid algorithm
Maxime Derome · Electronics Letters · 1993
A simple formula is derived giving e−1 mod s, in terms of modular addition, multiplication, and exponentiation operations, for any positive integer s not containing the prime factor e. These modular operations would be part of the instruction set of any hardware implementation of the RSA public key algorithm, making it particularly convenient for calculating RSA key pairs where one of the pair is a prime. The formula is extended to nonprime inverses.