Method and apparatus for performing modular division

1. An apparatus that performs modular division, comprising:

a register A that is initialized with a value X;

a register U that is initialized with a value Y;

a register B that is initialized with a value M;

a register V that is initialized with a value 0;

a temporary register H;

a temporary register L; and

an updating mechanism that is configured to iteratively reduce the contents of registers A and B to a value of one by applying a plurality of invariant operations to registers A, B, U and V;

wherein updating mechanism is configured to temporarily store A+B in the temporary register H;

wherein updating mechanism is configured to temporarily store U+V in the temporary register L.

2. The apparatus of claim 1 , wherein the initial values in the registers A, B, U and V satisfy invariant relationships.

3. The apparatus of claim 2 , wherein the invariant relationships include:

A*Y=U*X mod M; and

B*Y=V*X mod M.

4. The apparatus of claim 3 , wherein the updating mechanism is configured to maintain the invariant relationships between the values of registers A, B, U and V after application of the plurality of invariant operations.

5. The apparatus of claim 4 , wherein the plurality of invariant operations comprise:

if A is even and U is even, then A:=SHIFT(A), U:=SHIFT(U);

if A is even and U is odd, then A:=SHIFT(A), U:=SHIFT(U+M);

if B is even and V is even, then B:=SHIFT(B), V:=SHIFT(V);

if B is even and V is odd, then B:=SHIFT(B), V:=SHIFT(V+M);

if A>B, then A:=A+B and U:=U+V; and

if A<B, then B:=A+B and V:=U+V;

wherein the SHIFT operation denotes a right shift by one bit of the register contents.

6. The apparatus of claim 5 ,

wherein setting A=A+B and U=U+V involves first setting H=A+B and L=U+V, and later setting A=H and U=L if A>B; and

wherein setting B=A+B and V=U+V involves first setting H=A+B and L=U+V, and later setting B=H and V=L if A<B.

7. The apparatus of claim 6 , wherein the operations of setting H=A+B, setting L=U+V, and determining if A>B or if B>A take place concurrently.

8. The apparatus of claim 1 , wherein components of the updating mechanism operate asynchronously, without use of a centralized clock signal.

9. An apparatus that performs modular division, comprising:

a register A that is initialized with a value X;

a register U that is initialized with a value Y;

a register B that is initialized with a value M;

a register V that is initialized with a value 0;

wherein the initial values in the registers A, B, U and V satisfy invariant relationships, including, A*Y=U*X mod M, and B*Y=V*X mod M;

a temporary register H;

a temporary register L; and

an updating mechanism that is configured to iteratively reduce the contents of registers A and B to a value of one by applying a plurality of invariant operations to registers A, B, U and V;

wherein updating mechanism is configured to temporarily store A+B in the temporary register H;

wherein updating mechanism is configured to temporarily store U+V in the temporary register L;

wherein the updating mechanism is configured to maintain the invariant relationships between the registers A, B, U and V after application of the plurality of invariant operations.

10. The apparatus of claim 9 , wherein the plurality of invariant operations comprise:

if A is even and U is even, then A:=SHIFT(A), U:=SHIFT(U);

if A is even and U is odd, then A:=SHIFT(A), U:=SHIFT(U+M);

if B is even and V is even, then B:=SHIFT(B), V:=SHIFT(V);

if B is even and V is odd, then B:=SHIFT(B), V:=SHIFT(V+M);

if A>B, then A:=A+B and U:=U+V; and

if A<B, then B:=A+B and V:=U+V;

wherein the SHIFT operation denotes a right shift by one bit of the register contents.

11. The apparatus of claim 10 ,

wherein setting A=A+B and U=U+V involves first setting H=A+B and L=U+V, and later setting A=H and U=L if A>B; and

wherein setting B=A+B and V=U+V involves first setting H=A+B and L=U+V, and later setting B=H and V=L if A<B.

12. The apparatus of claim 11 , wherein the operations of setting H=A+B, setting L=U+V, and determining if A>B or if B>A take place concurrently.

13. The apparatus of claim 9 , wherein components of the updating mechanism operate asynchronously, without use of a centralized clock signal.

14. A method for performing a modular division, comprising:

initializing a register A with a value X;

initializing a register U with a value Y;

initializing a register B with a value M;

initializing a register V with a value 0; and

iteratively reducing the contents of registers A and B to a value of one by applying a plurality of invariant operations to registers A, B, U and V;

wherein applying the plurality of invariant operations involves temporarily storing A+B in a temporary register H;

wherein applying the plurality of invariant operations involves temporarily storing U+V in a temporary register L.

15. The method of claim 14 , wherein the initial values in the registers A, B, U and V satisfy invariant relationships.

16. The method of claim 15 , wherein the invariant relationships include:

A*Y=U*X mod M; and

B*Y=V*X mod M.

17. The method of claim 16 , wherein the plurality of invariant operations maintain the invariant relationships between the registers A, B, U and V.

18. The method of claim 17 , wherein the plurality of invariant operations comprise:

if A is even and U is even, then A:=SHIFT(A), U:=SHIFT(U);

if A is even and U is odd, then A:=SHIFT(A), U:=SHIFT(U+M);

if B is even and V is even, then B:=SHIFT(B), V:=SHIFT(V);

if B is even and V is odd, then B:=SHIFT(B), V:=SHIFT(V+M);

if A>B, then A:=A+B and U:=U+V; and

if A<B, then B:=A+B and V:=U+V;

wherein the SHIFT operation denotes a right shift by one bit of the register contents.

19. The method of claim 18 ,

wherein setting A=A+B and U=U+V involves first setting H=A+B and L=U+V, and later setting A=H and U=L if A>B; and

wherein setting B=A+B and V=U+V involves first setting H=A+B and L=U+V, and later setting B=H and V=L if A<B.

20. The method of claim 19 , wherein the operations of setting H=A+B, setting L=U+V, and determining if A>B or if B>A take place concurrently.

21. The method of claim 14 , wherein operations involved in performing the method take place asynchronously, without use of a centralized clock signal.