Abstract :
The Montgomery residue number system (MRNS) for long word-length arithmetic is introduced. MRNS, a modification of the residue number system (RNS), represents a long integer as a set of smaller Montgomery residues. Long integer addition, subtraction and multiplication can then be performed using hardware-efficient Montgomery operations applied independently to each of the residues. An MRNS hardware architecture suitable for incorporation on a microprocessor data path is also proposed
