High-speed modulo exponentiator device

A method for performing a modulo exponentiation function of the form C=B.sup.E (Modulo M), wherein E is a large positive integer and B and M are large integers, as a series of modulo multiplication operations of the form P=(X * Y) (Modulo M), wherein X and Y are operands of the exponentiation function in binary form, comprising the steps of:

• (a) providing an X register, a Y register, and an A register, and control means for carrying out a loop computation using said X, Y, and A registers;
• (b) computing an xf factor based upon three most significant bits of Y,
• (c) computing 4*A+xf*X and transferring the result to the A register,
• (d) determining an mf factor based upon a comparison of A with selected threshold values of M,
• (e) computing A+mf*M and transferring the result to the A register,
• (f) shifting the bits of the Y register two bits to the left (two most significant bits of Y) and returning to step (a) above until said loop computation is completed, and
• (g) providing an output from the A register at the completion of said loop computation as the result of the modulo multiplication operation.

A high-speed modulo exponentiator device for performing a modulo exponentiation function of the form C=B.sup.E (Modulo M), wherein E is a large positive integer and B and M are large integers, as a series of modulo multiplication operations of the form P=(X * Y) (Modulo M), wherein X and Y are operands of the exponentiation function in binary form, based upon an extended Booth algorithm, comprising:

• digital integrated circuit ("IC") means including an X register, a Y register, and an A register having bit lengths of n and initialized with operand X, operand Y, and 0, respectively, said X, Y, and A registers being interconnected and operative with control means for carrying out a loop computation using said X, Y, and A registers for k=(n-1)/2, . . . , 0, when n is an odd number, and k=(n-2)/2, . . . , 0, when n is an even number, wherein said control means includes:
• (a) first register control means for computing xf(k)=-2*y(MSB)+1*y(MSB-1)+1*y(MSB-2), where y(MSB), y(MSB-1), y(MSB-2) are three most significant bits of Y;
• (b) second register control means for computing 4*A+xf(k)*X and transferring the result to the A register;
• (c) third register control means for determining mf(k), wherein mf(k) is a multiple of -2, -1, 0, 1, or 2 times 128, depending upon a comparison of eight most-significant bits of A with four selected threshold values of M;
• (d) fourth register control means for computing A+mf(k)*M and transferring the result to the A register;
• and
• (e) fifth register control means for shifting the bits of the Y register two bits to the left (two most significant bits of Y) and returning control to said first register control means until said loop computation is completed.