Patent ID: 8090757

Claim:
A method in a modulo processor of performing a modulo N exponentiation of a first operand (A) raised to an exponent (d), wherein N is equal to a product of a first integer (p) and a second integer (q), and wherein a first variable (dp=d mod(p−1)), a second variable (dq=d mod(q−1)), and a third variable (Q=q −1 mod p) are known, the method comprising: computing, by the modulo processor, A p =A dp mod p; computing, by the modulo processor, A q =A dq mod q; computing, by the modulo processor, (Y 0 )=(A p −A q ) mod p; computing, by the modulo processor, Y 1 =(QY 0 ) mod p; computing, by the modulo processor, Y 2 =(qY 1 ); computing, by the modulo processor, X=(Y 2 +A q ) mod N, wherein X is equivalent to A d mod N.