Patent ID: 6963977

Claim:
A method for computing A E modulo N, where A, E and N are integers, with A<2N, all having binary representations, and where n is the number of bits in the binary representation of N, and where E = ∑ i = 0 t ⁢ e i ⁢ 2 i , and where t is the number of bits in the binary representation of E, and where m and k are two positive integers such that mk≧n+2, said method comprising the steps of: providing a signal representing a constant, C, which is equal to 2 +2mk mod N; multiplying said value A by said constant C using a circuit which accepts two input operands and which produces an output result value Z 0 given by A C 2 −mk modulo N; storing said value Z 0 in a first register and in a second register; for sequential values of an index i running from 1 to t, repeatedly using the value in said second register as both of said operands for said circuit, with the output of said circuit being stored back into said second register and, when e l+i is 1, using again the contents of said second register as one input operand to said circuit with said other input operand being said Z 0 value in said first register with the output of said circuit being stored in said first register; upon completion of said repetition, operating said circuit with the contents of said second register as one input operand with the constant 1 as said other input operand; and storing the output of said circuit in at least one of said registers, whereby said at least one register contains the binary representation of A E modulo N.