Scheme for computing Montgomery division and Montgomery inverse realizing fast implementation

• US 6,088,453 A
• Filed: 01/26/1998
• Issued: 07/11/2000
• Est. Priority Date: 01/27/1997
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Shimbo, Atsushi
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US09/013,209
• Time in Patent Office: 897 Days
• Field of Search: 713/100, 380/28, 708/135, 708/211, 708/490, 708/491, 708/492, 708/523, 708/625, 708/653, 708/654, 708/655, 708/656, 712/14
• US Class Current: 380/28
• CPC Class Codes: G06F 7/721 Modular inversion, reciprocal or quotient calculation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/728 using Montgomery reduction

Abstract

A scheme for performing high speed Montgomery division within the Montgomery space. Montgomery division Y=B·A^-1 ·2ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦A≦N, a positive integer B, and an integer n which is satisfying n≧L where L is a bit length of N in binary expression, is performed by obtaining a Montgomery inverse X=A^-1 ·2²ⁿ mod N from inputs A and N, and obtaining the Montgomery division Y=B·X·2^-n mod N from the Montgomery inverse X and inputs B and N. Montgomery inverse X=A^-1 ·2²ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦A<N, and an integer n which satisfies n≧L where L is a bit length of N in binary expression, is determined by obtaining an intermediate result C=A^-1 ·2^k mod N and a parameter k satisfying L≦k≦2L from inputs A and N, and obtaining the Montgomery inverse X=C·2^2n-k mod N from the intermediate result C and the parameter k and input N.

Claims

1. A Montgomery division device for computing a Montgomery division Y=B·

A^-1 ·

2ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the device comprising;

a Montgomery inverse calculation unit for obtaining a Montgomery inverse X=A^-1 ·

2²ⁿ mod N from inputs A and N; and

a Montgomery multiplication unit for obtaining the Montgomery division Y=B·

X·

2^-n mod N from the Montgomery inverse X obtained by the Montgomery inverse calculation unit and inputs B and N.

2. The device of claim 1, wherein the Montgomery inverse calculation unit includes:

an inverse calculation unit for obtaining an intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N; and

an inverse correction unit for obtaining the Montgomery inverse X=C·

2^2n-k mod N from the intermediate result C and the parameter k obtained by the inverse calculation unit and input N.

3. A Montgomery division device for computing a Montgomery division Y=B·

A^-1 ·

2ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the device comprising;

an inverse calculation unit for obtaining a first intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N;

a Montgomery multiplication unit for obtaining a second intermediate result D=B·

C·

2^-n mod N from the first intermediate result C obtained by the inverse calculation unit and input B and N; and

an inverse correction unit for obtaining the Montgomery division Y=D·

2^2n-k mod N from the second intermediate result D obtained by the Montgomery multiplication unit, the parameter k obtained by the inverse calculation unit and input N.

4. A Montgomery inverse calculation device for computing a Montgomery inverse X=A^-1 ·

2²ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the device comprising;

an inverse calculation unit for obtaining an intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N; and

an inverse correction unit for obtaining the Montgomery inverse X=C·

2^2n-k mod N from the intermediate result C and the parameter k obtained by the inverse calculation unit and input N.

5. The device of claim 4, wherein the inverse calculation unit and the inverse correction unit are formed by:

a plurality of registers for internally registering intermediate variables;

a bit shifter for right/left shifting a value registered in each of said registers;

an adder/subtracter for adding/subtracting values registered in two of said registers; and

a judgement unit for comparing values registered in two of said registers, and for judging a value of a specific bit position in each of said registers.

6. The device of claim 4, wherein the inverse calculation unit carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U, left shifting S and incrementing k by one when a least significant bit of U is 0, and right shifting V, left shifting T and incrementing k by one when a least significant bit of V is 0;

a processing for subtracting V from U, right shifting U, adding S to T, left shifting S and incrementing k by one when a least significant bit of U is 1, a least significant bit of V is 1 and U>

V; and

a processing for subtracting U from V, right shifting V, adding T to S, left shifting T and incrementing k by one when a least significant bit of U is 1, a least significant bit of V is 1 and U≦

V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

7. The device of claim 4, wherein the inverse calculation unit carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U by w1 bits, left shifting S by w1 bits and incrementing k by w1 when w1 is not zero, where w1 is a bit length of consecutive 0 from a least significant bit of U, and right shifting V by w2 bits, left shifting T by w2 bits and incrementing k by w2 when w2 is not zero, where w2 is a bit length of consecutive 0 from a least significant bit of V;

a processing for subtracting V from U, right shifting U, adding S to T, left shifting S and incrementing k by one when w1 is zero, w2 is zero and U>

V; and

a processing for subtracting U from V, right shifting V, adding T to S, left shifting T and incrementing k by one when w1 is zero, w2 is zero and U≦

V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

8. The device of claim 4, wherein the inverse calculation unit carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U by w1 bits, left shifting S by w1 bits and incrementing k by w1 when w1 is not zero, where w1 is a bit length of consecutive 0 from a least significant bit of U, and right shifting V by w2 bits, left shifting T by w2 bits and incrementing k by w2 when w2 is not zero, where w2 is a bit length of consecutive 0 from a least significant bit of V;

a processing for subtracting V from U, right shifting U by w3 bits, adding S to T, left shifting S by w3 bits and incrementing k by w3 when w1 is zero, w2 is zero and U>

V, where w3 is a bit length of consecutive 0 from a least significant bit of a value obtained by subtracting V from U; and

a processing for subtracting U from V, right shifting V by w4 bits, adding T to S, left shifting T by w4 bits and incrementing k by w4 when w1 is zero, w2 is zero and U≦

V, where w4 is a bit length of consecutive 0 from a least significant bit of a value obtained by subtracting U from V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

9. The device of claim 4, wherein the inverse correction unit carries out an operation formed by:

an initialization processing for setting an initial state of i=0 for a register value i and setting the intermediate result C obtained by the inverse calculation unit to a register value T;

a loop processing to be iterated while i<

2n-k, for left shifting T, and then subtracting N from T and incrementing i by one when T≧

N or incrementing i by one when T<

N; and

a calculation processing for setting the Montgomery inverse X to be a value of T obtained by the loop processing when i becomes equal to 2n-k.

10. The device of claim 4, wherein the inverse correction unit carries out an operation formed by:

an initialization processing for setting an initial state of i=0 for a register value i and setting the intermediate result C obtained by the inverse calculation unit to a register value T;

a loop processing to be iterated while i<

2n-k, including;

a processing for left shifting T by one bit, subtracting N from T and incrementing i by one when w1 is zero, where w1 is a bit length of consecutive 0 from a most significant bit of T,

a processing for setting w2 to be 2n-k-i, left shifting T by w2 bits and setting i to be 2n-k when w1 is not zero and i+w1>

2n-k;

a processing for left shifting T by w1 bits, and then subtracting N from T and incrementing i by w1 when T≧

N or incrementing i by w1 when T<

N; and

a calculation processing for setting the Montgomery inverse X to be a value of T obtained by the loop processing when i becomes equal to 2n-k.

11. The device of claim 4, wherein the inverse calculation unit and the inverse correction unit are formed by:

a U register for registering a register value U which is initially set to be N;

a V register for registering a register value V which is initially set to be A;

a T register for registering a register value T which is initially set to be 0;

an S register for registering a register value S which is initially set to be 1;

a k register for registering a register value k which is initially set to be 0;

a bit shifter for carrying out a right shifting of U, a right shifting of V, the left shifting of T, and a left shifting of S;

an adder/subtracter for carrying out a subtraction of V from U, a subtraction of U from V, an addition of S to T, an addition of T to S, a subtraction of N from T, a subtraction of T from N, and an addition of 1 to k;

a judgement unit for judging whether a least significant bit of U is 0 or not, whether a least significant bit of V is 0 or not, whether V is 0 or not, and whether T is greater than or equal to N or not; and

a control unit for controlling the bit shifter, the adder/subtractor, and the judgement unit.

12. A method for computing a Montgomery division Y=B·

A^-1 ·

2ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the method comprising the steps of;

(a) obtaining a Montgomery inverse X=A^-1 ·

2²ⁿ mod N from inputs A and N; and

(b) obtaining the Montgomery division Y=B·

X·

2^-n mod N from the Montgomery inverse X obtained by the step (a) and inputs B and N.

13. The method of claim 12, wherein the step (a) includes the steps of:

(a1) obtaining an intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N; and

(a2) obtaining the Montgomery inverse X=C·

2^2n-k mod N from the intermediate result C and the parameter k obtained by the step (a1) and input N.

14. A method for computing a Montgomery division Y=B·

A^-1 ·

2ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A≦

N, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the method comprising the steps of;

(a) obtaining a first intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N;

(b) obtaining a second intermediate result D=B·

C·

2^-n mod N from the first intermediate result C obtained by the step (a) and input B and N; and

(c) obtaining the Montgomery division Y=D·

2^2n-k mod N from the second intermediate result D obtained by the step (b), the parameter k obtained by the step (a) and input N.

15. A method for computing a Montgomery inverse X=A^-1 ·

2²ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the method comprising the steps of;

(a) obtaining an intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N; and

(b) obtaining the Montgomery inverse X=C·

2^2n-k mod N from the intermediate result C and the parameter k obtained by the step (a) and input N.

16. The method of claim 15, wherein the step (a) carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U, left shifting S and incrementing k by one when a least significant bit of U is 0, and right shifting V, left shifting T and incrementing k by one when a least significant bit of V is 0;

a processing for subtracting V from U, right shifting U, adding S to T, left shifting S and incrementing k by one when a least significant bit of U is 1, a least significant bit of V is 1 and U>

V; and

a processing for subtracting U from V, right shifting V, adding T to S, left shifting T and incrementing k by one when a least significant bit of U is 1, a least significant bit of V is 1 and U≦

V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

17. The method of claim 15, wherein the step (a) carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U by w1 bits, left shifting S by w1 bits and incrementing k by w1 when w1 is not zero, where w1 is a bit length of consecutive 0 from a least significant bit of U, and right shifting V by w2 bits, left shifting T by w2 bits and incrementing k by w2 when w2 is not zero, where w2 is a bit length of consecutive 0 from a least significant bit of V;

a processing for subtracting V from U, right shifting U, adding S to T, left shifting S and incrementing k by one when w1 is zero, w2 is zero and U>

V; and

a processing for subtracting U from V, right shifting V, adding T to S, left shifting T and incrementing k by one when w1 is zero, w2 is zero and U≦

V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

18. The method of claim 15, wherein the step (a) carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U by w1 bits, left shifting S by w1 bits and incrementing k by w1 when w1 is not zero, where w1 is a bit length of consecutive 0 from a least significant bit of U, and right shifting V by w2 bits, left shifting T by w2 bits and incrementing k by w2 when w2 is not zero, where w2 is a bit length of consecutive 0 from a least significant bit of V;

a processing for subtracting V from U, right shifting U by w3 bits, adding S to T, left shifting S by w3 bits and incrementing k by w3 when w1 is zero, w2 is zero and U>

V, where w3 is a bit length of consecutive 0 from a least significant bit of a value obtained by subtracting V from U; and

a processing for subtracting U from V, right shifting V by w4 bits, adding T to S, left shifting T by w4 bits and incrementing k by w4 when w1 is zero, w2 is zero and U≦

V, where w4 is a bit length of consecutive 0 from a least significant bit of a value obtained by subtracting U from V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

19. The method of claim 15, wherein the step (b) carries out an operation formed by:

an initialization processing for setting an initial state of i=0 for a register value i and setting the intermediate result C obtained by the inverse calculation unit to a register value T;

a loop processing to be iterated while i<

2n-k, for left shifting T, and then subtracting N from T and incrementing i by one when T≧

N or incrementing i by one when T<

N; and

a calculation processing for setting the Montgomery inverse X to be a value of T obtained by the loop processing when i becomes equal to 2n-k.

20. The method of claim 15, wherein the step (b) carries out an operation formed by:

an initialization processing for setting an initial state of i=0 for a register value i and setting the intermediate result C obtained by the inverse calculation unit to a register value T;

a loop processing to be iterated while i<

2n-k, including;

a processing for left shifting T by one bit, subtracting N from T and incrementing i by one when w1 is zero, where w1 is a bit length of consecutive 0 from a most significant bit of T,

a processing for setting w2 to be 2n-k-i, left shifting T by w2 bits and setting i to be 2n-k when w1 is not zero and i+w1>

2n-k;

a processing for left shifting T by w1 bits, and then subtracting N from T and incrementing i by w1 when T≧

N or incrementing i by w1 when T<

N; and

a calculation processing for setting the Montgomery inverse X to be a value of T obtained by the loop processing when i becomes equal to 2n-k.

21. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for computing a Montgomery division Y=B·

A^-1 ·

2ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the computer readable program code means includes;

first computer readable program code means for causing said computer to obtain a Montgomery inverse X=A^-1 ·

2²ⁿ mod N from inputs A and N; and

second computer readable program code means for causing said computer to obtain the Montgomery division Y=B·

X·

2^-n mod N from the Montgomery inverse X obtained by the first computer readable program code means and inputs B and N.

22. The article of manufacture of claim 21, wherein the first computer readable program code means includes:

first computer readable sub-program code means for causing said computer to obtain an intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N; and

second computer readable sub-program code means for causing said computer to obtain the Montgomery inverse X=C·

2^2n-k mod N from the intermediate result C and the parameter k obtained by the first computer readable sub-program code means and input N.

23. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for computing a Montgomery division Y=B·

A^-1 ·

2ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the computer readable program code means includes;

first computer readable program code means for causing said computer to obtain a first intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N;

second computer readable program code means for causing said computer to obtain a second intermediate result D=B·

C·

2^-n mod N from the first intermediate result C obtained by the first computer readable program code means and input B and N; and

third computer readable program code means for causing said computer to obtain the Montgomery division Y=D·

2^2n-k mod N from the second intermediate result D obtained by the second computer readable program code means, the parameter k obtained by the first computer readable program code means and input N.

24. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for computing a Montgomery inverse X=A^-1 ·

2²ⁿ mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0≦

A<

N, and an integer n which is satisfying n≧

L where L is a bit length of N in binary expression, the computer readable program code means includes;

first computer readable program code means for causing said computer to obtain an intermediate result C=A^-1 ·

2^k mod N and a parameter k satisfying L≦

k≦

2L from inputs A and N; and

second computer readable program code means for causing said computer to obtain the Montgomery inverse X=C·

2^2n-k mod N from the intermediate result C and the parameter k obtained by the first computer readable program code means and input N.

25. The article of manufacture of claim 24, wherein the first computer readable program code means carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U, left shifting S and incrementing k by one when a least significant bit of U is 0, and right shifting V, left shifting T and incrementing k by one when a least significant bit of V is 0;

a processing for subtracting V from U, right shifting U, adding S to T, left shifting S and incrementing k by one when a least significant bit of U is 1, a least significant bit of V is 1 and U>

V; and

a processing for subtracting U from V, right shifting V, adding T to S, left shifting T and incrementing k by one when a least significant bit of U is 1, a least significant bit of V is 1 and U≦

V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

26. The article of manufacture of claim 24, wherein the first computer readable program code means carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U by w1 bits, left shifting S by w1 bits and incrementing k by w1 when w1 is not zero, where w1 is a bit length of consecutive 0 from a least significant bit of U, and right shifting V by w2 bits, left shifting T by w2 bits and incrementing k by w2 when w2 is not zero, where w2 is a bit length of consecutive 0 from a least significant bit of V;

a processing for subtracting V from U, right shifting U, adding S to T, left shifting S and incrementing k by one when w1 is zero, w2 is zero and U>

V; and

a processing for subtracting U from V, right shifting V, adding T to S, left shifting T and incrementing k by one when w1 is zero, w2 is zero and U≦

V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

27. The article of manufacture of claim 24, wherein the first computer readable program code means carries out an operation formed by:

an initialization processing for setting an initial state of U=N, V=A, T=0, S=1 and k=0 in binary expression for register values U, V, T, S and k;

a loop processing to be iterated while V>

0, including;

a processing for right shifting U by w1 bits, left shifting S by w1 bits and incrementing k by w1 when w1 is not zero, where w1 is a bit length of consecutive 0 from a least significant bit of U, and right shifting V by w2 bits, left shifting T by w2 bits and incrementing k by w2 when w2 is not zero, where w2 is a bit length of consecutive 0 from a least significant bit of V;

a processing for subtracting V from U, right shifting U by w3 bits, adding S to T, left shifting S by w3 bits and incrementing k by w3 when w1 is zero, w2 is zero and U>

V, where w3 is a bit length of consecutive 0 from a least significant bit of a value obtained by subtracting V from U; and

a processing for subtracting U from V, right shifting V by w4 bits, adding T to S, left shifting T by w4 bits and incrementing k by w4 when w1 is zero, w2 is zero and U≦

V, where w4 is a bit length of consecutive 0 from a least significant bit of a value obtained by subtracting U from V; and

a calculation processing to be carried out when V becomes equal to 0, for subtracting N from T and then setting the intermediate result C to be a value obtained by subtracting T from N when T≧

N, or setting the intermediate result C to be a value obtained by subtracting T from N when T<

N.

28. The article of manufacture of claim 24, wherein the second computer readable program code means carries out an operation formed by:

an initialization processing for setting an initial state of i=0 for a register value i and setting the intermediate result C obtained by the inverse calculation unit to a register value T;

a loop processing to be iterated while i<

2n-k, for left shifting T, and then subtracting N from T and incrementing i by one when T≧

N or incrementing i by one when T<

N; and

a calculation processing for setting the Montgomery inverse X to be a value of T obtained by the loop processing when i becomes equal to 2n-k.

29. The article of manufacture of claim 24, wherein the second computer readable program code means carries out an operation formed by:

an initialization processing for setting an initial state of i=0 for a register value i and setting the intermediate result C obtained by the inverse calculation unit to a register value T;

a loop processing to be iterated while i<

2n-k, including;

a processing for left shifting T by one bit, subtracting N from T and incrementing i by one when w1 is zero, where w1 is a bit length of consecutive 0 from a most significant bit of T,

a processing for setting w2 to be 2n-k-i, left shifting T by w2 bits and setting i to be 2n-k when w1 is not zero and i+w1>

2n-k;

a processing for left shifting T by w1 bits, and then subtracting N from T and incrementing i by w1 when T≧

N or incrementing i by w1 when T<

N; and

a calculation processing for setting the Montgomery inverse X to be a value of T obtained by the loop processing when i becomes equal to 2n-k.

30. A method for implementing basic operations of an elliptic curve cryptosystem, comprising the steps of:

converting parameters of the basic operations of the elliptic curve cryptosystem from Zp, integers modulo p, over which elliptic curves are defined, into a Montgomery space;

executing the basic operations of the elliptic curve cryptosystem on input data of the elliptic curve cryptosystem in terms of Montgomery arithmetic system operations defined on the Montgomery space using the parameters converted by the converting step; and

inversely converting operation results of the basic operations of the elliptic curve cryptosystem obtained by the executing step from the Montgomery space into Zp so as to obtain output data of the elliptic curve cryptosystem.

31. The method of claim 30, wherein the Montgomery arithmetic system includes calculation of a Montgomery inverse X=A^-1 ·

2²ⁿ mod p for a positive integer A which is relatively prime with respect to p and satisfying 0≦

A<

p, and an integer n which is satisfying n≧

L where L is a bit length of p in binary expression, by the steps of;

(a) obtaining an intermediate result C=A^-1 ·

2^k mod p and a parameter k satisfying L≦

k≦

2L from inputs A and p; and

(b) obtaining the Montgomery inverse X=C·

2^2n-k mod p from the intermediate result C and the parameter k obtained by the step (a) and input p.

32. The method of claim 30, wherein the Montgomery arithmetic system includes calculation of a Montgomery division Y=B·

A^-1 ·

2ⁿ mod p for a positive integer A which is relatively prime with respect to p and satisfying 0≦

A<

p, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of p in binary expression, by the steps of;

(a) obtaining a Montgomery inverse X=A^-1 ·

2²ⁿ mod p from inputs A and p; and

(b) obtaining the Montgomery division Y=B·

X·

2^-n mod p from the Montgomery inverse X obtained by the step (a) and inputs B and p.

33. The method of claim 32, wherein the step (a) includes the steps of:

(a1) obtaining an intermediate result C=A^-1 ·

2^k mod p and a parameter k satisfying L≦

k≦

2L from inputs A and p; and

(a2) obtaining the Montgomery inverse X=C·

2^2n-k mod p from the intermediate result C and the parameter k obtained by the step (a1) and input p.

34. The method of claim 30, wherein the Montgomery arithmetic system includes calculation of a Montgomery division Y=B·

A^-1 ·

2ⁿ mod p for a positive integer A which is relatively prime with respect to p and satisfying 0≦

A<

p, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of p in binary expression, by the steps of;

(a) obtaining a first intermediate result C=A^-1 ·

2^k mod p and a parameter k satisfying L≦

k≦

2L from inputs A and p;

(b) obtaining a second intermediate result D=B·

C·

2^-n mod p from the first intermediate result C obtained by the step (a) and input B and p; and

(c) obtaining the Montgomery division Y=D·

2^2n-k mod p from the second intermediate result D obtained by the step (b), the parameter k obtained by the step (a) and input p.

35. The method of claim 30, wherein the Montgomery arithmetic system includes addition, subtraction, and multiplication in the Montgomery space in a case where the basic operations include addition of the elliptic curves using projective coordinates.

36. The method of claim 30, wherein the Montgomery arithmetic system includes addition, subtraction, multiplication, and division in the Montgomery space, in a case where the basic operations include addition of the elliptic curves using affine coordinates.

37. A method for implementing basic operations of an elliptic curve cryptosystem, comprising the steps of:

defining parameters of the basic operations of the elliptic curve cryptosystem in a Montgomery space over which elliptic curves are defined; and

executing the basic operations of the elliptic curve cryptosystem on input data of the elliptic curve cryptosystem in terms of Montgomery arithmetic system operations defined on the Montgomery space using the parameters defined by the defining step so as to obtain output data of the elliptic curve cryptosystem given by operation results for the basic operations of the elliptic curve cryptosystem in the Montgomery space.

38. The method of claim 37, wherein the Montgomery arithmetic system includes calculation of a Montgomery inverse X=A^-1 ·

2²ⁿ mod p for a positive integer A which is relatively prime with respect to p and satisfying 0≦

A<

p, and an integer n which is satisfying n≧

L where L is a bit length of p in binary expression, by the steps of;

(a) obtaining an intermediate result C=A^-1 ·

2^k mod p and a parameter k satisfying L≦

k≦

2L from inputs A and p; and

(b) obtaining the Montgomery inverse X=C·

2^2n-k mod p from the intermediate result C and the parameter k obtained by the step (a) and input p.

39. The method of claim 37, wherein the Montgomery arithmetic system includes calculation of a Montgomery division Y=B·

A^-1 ·

2ⁿ mod p for a positive integer A which is relatively prime with respect to p and satisfying 0≦

A<

p, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of p in binary expression, by the steps of;

(a) obtaining a Montgomery inverse X=A^-1 ·

2²ⁿ mod p from inputs A and p; and

(b) obtaining the Montgomery division Y=B·

X·

2^-n mod p from the Montgomery inverse X obtained by the step (a) and inputs B and p.

40. The method of claim 39, wherein the step (a) includes the steps of:

(a1) obtaining an intermediate result C=A^-1 ·

2^k mod p and a parameter k satisfying L≦

k≦

2L from inputs A and p; and

(a2) obtaining the Montgomery inverse X=C·

2^2n-k mod p from the intermediate result C and the parameter k obtained by the step (a1) and input p.

41. The method of claim 37, wherein the Montgomery arithmetic system includes calculation of a Montgomery division Y=B·

A^-1 ·

2ⁿ mod p for a positive integer A which is relatively prime with respect to p and satisfying 0≦

A<

p, a positive integer B, and an integer n which is satisfying n≧

L where L is a bit length of p in binary expression, by the steps of;

(a) obtaining a first intermediate result C=A^-1 ·

2^k mod p and a parameter k satisfying L≦

k≦

2L from inputs A and p;

(b) obtaining a second intermediate result D=B·

C·

2^-n mod p from the first intermediate result C obtained by the step (a) and input B and p; and

(c) obtaining the Montgomery division Y=D·

2^2n-k mod p from the second intermediate result D obtained by the step (b), the parameter k obtained by the step (a) and input p.

42. The method of claim 37, wherein the Montgomery arithmetic system includes addition, subtraction, and multiplication in the Montgomery space in a case where the basic operations include addition of the elliptic curves using projective coordinates.

43. The method of claim 37, wherein the Montgomery arithmetic system includes addition, subtraction, multiplication, and division in the Montgomery space in a case where the basic operations include addition of the elliptic curves using affine coordinates.