Modular multiplication in the Montgomery residue number system
Braden J. Phillips · 2001
This paper considers the evaluation of long wordlength modular products. An algorithm is described in which long wordlength (e.g. 1024-bit) integers are represented by short-wordlength (e.g. 32-bit) Montgomery (1985) residues. Long integer modular multiplication is performed using only short-wordlength Montgomery operations. Architectures are proposed that take advantage of the parallelism afforded by this scheme.