Circuit and method for performing multiple modulo mathematic operations
View Patent ↗A multi-function modulo processor architecture is capable of performing multiple modulo mathematic operations. The modulo processor includes a pipeline processing portion that iteratively computes a running partial modulo product using the operands of a modulo mathematic argument to obtain one or more final partial modulo products. The final partial modulo product is post-processed to obtain the final result.
1. 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.