Patent ID: 7627114

Claim:
A method for producing A mod N, where A is a binary number considered as having n blocks with k bits each and where N is a binary number considered as having m blocks of k bits each, said method comprising the steps of: loading the value R N =R m+1 mod N, where R=2 k , into a first register; loading a second register for the variable Z with the high order m blocks for A; and for values of i ranging from n−1 to m+1, replacing the value in said second register with the value Z−Z i R i +Z i R N R i−m−1 , but if adding Z 1 R N and the low order (m+1)k bits of the second register produces a carry out indication, replacing the value in said second register instead with the value Z−Z i R i +Z i R N R i−m−1 −R i +R N R i−m−1 , where Z is the current value in said second register and Z i is the high order k bits in said second register, and shifting said second register left and shifting into said second register, on the right thereof, the next k bit block of A.