Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-05-17
2004-07-13
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06763366
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to extended greatest common divisor algorithms and in particular to an improved Jebelean greatest common divisor algorithm that efficiently calculates arithmetic inverses. (The extended greatest common divisor algorithm calculates 3 integers from two positive integers as follows: [&agr;,&bgr;,d]=GCD(u,v) such that d|u, d|v, ∀e>d:
(e|u & e|v) and &agr;·u+&bgr;·v=d.)
Modular arithmetic is used in many applications such as encryption algorithms and the generation of error correcting codes. When the modulus is a prime number (p), the operations of addition, subtraction, multiplication and division with nonzero elements as well as the associative, commutative and distributive properties are defined over the set of numbers from zero to p. This set of numbers defines a Finite field modulo p, F
P
. They are often referred as “Prime Fields”.
Extended GCD algorithms are commonly used to find inverses in large Finite fields, which are of interest for encryption purposes. One type of encryption algorithm encrypts data using exponentiation over a large finite field, relying on the inherent difficulty of the inverse of exponentiation, the discrete logarithm problem, to hold the data secure. Encryption performed on a large finite field (having more elements) is more secure than encryption performed on a small field. One problem with using large finite fields, however, is the difficulty in performing even simple arithmetic operations on the large numbers in the field. Typical numbers used in data encryption have hundreds of bits. These numbers are too large to be easily handled by commonly available microprocessors that are limited to 32 or 64-bit arithmetic. This is especially true of exponentiation where a 100-bit number is raised to the power of second 100-bit number and the result is determined modulo a third 100-bit number. As described below, calculations using these large numbers are typically handled using multiprecision arithmetic.
Another type of encryption algorithm uses multiplication by an integer number within an elliptic curve group, where the group operation is symbolized by addition. (It is the same as exponentiation in groups, where the group operation is denoted by multiplication.) An elliptic curve group is defined on ordered pairs of points of a grid that lie on an elliptic curve defined by an equation such as equation (1).
Y
2
=(
X
3
+A·X+B
)
modulo P
(1)
where P is a prime number equal to the number of rows and the number of columns in the grid together with a special point ∘, called the point at infinity. In elliptic curve cryptography, an encryption key is generated by multiplying a generator point P by itself k times. (i.e. Q=kP, where Q is the encryption key).
Multiplication by an integer in the elliptic curve group is modeled as repeated addition of the group elements to themselves. Addition of a group element to itself in an elliptic curve group, however, is not as simple as integer addition. Because points in the elliptic curve group are ordered pairs, addition may be represented as, (X
1
,Y
1
)+(X
2
,Y
2
)=(X
3
,Y
3
) where X
3
, Y
3
are defined by equations (2) and (3) if neither of the points is the point at infinity (in which case the definition states that (X
1
,Y
1
)+∘=(X
1
,Y
1
)). L a variable used in equations (2) and (3) is defined by equation (4).
X
3
=L
2
−X
1
−X
2
modulo P
(2)
Y
3
=L
(
X
1
−X
3
)−
Y
1
modulo P
(3)
L
=(
Y
2
−Y
1
)/(
X
2
−X
1
)
modulo P
(4)
If X
1
=X
2
and Y
1
=Y
2
, X
3
and Y
3
are defined by equations (5) and (6).
X
3
=L
2
−2
X
1
modulo P
(5)
Y
3
=L
(
X
1
−X
3
)−
Y
1
modulo P
(6)
L
=(3
X
1
2
+A
)/2
Y
1
(7)
Where A is the coefficient of X in equation (1).
Thus, addition of two members of the elliptic curve group involves a modular integer division operation. In modular arithmetic, division of a value N by a value D means multiplication of N by the arithmetic inverse of D, D
−1
. It is known that an arithmetic inverse of a number in a finite field may be calculated using the extended greatest common divisor algorithm.
FIG. 1
is a flow chart diagram, which illustrates an extended greatest common divisor (GCD) algorithm known as Euclid's or Euclidean algorithm. The algorithm shown in
FIG. 1
calculates the greatest common divisor of U and V where U is greater than V. This algorithm relies on the property that if U and V have a common divisor D so does U−V, U−2V and so on. Thus, using only subtraction, one can calculate the GCD of U and V. GCD algorithms run faster when they can combine multiple subtractions in a single step. In general, GCD algorithms operate by successively reducing the values of U and V, combining multiple subtraction operations where possible, while maintaining the equations (7), (8) and (9)
U
1
·U+U
2·
V=U
3 (7)
V
1·
U+V
2·
V=V
3 (8)
T
1·
U+T
2·
V=T
3 (9)
Where U≧V and (U1, U2, U3) and (V1, V2, V3) are initially assigned the values of (1, 0, U) and (0, 1, V), respectively. If the algorithm is used to calculate the greatest common divisor of a prime number P and a value X, then, upon termination, U3=GCD(P, X)=1 and U2=X
−1
MOD P. In general terms, GCD algorithms operate by repetitively reducing the number of bits in the larger value, U, and switching the two values. Thus, the algorithm successively reduces the values of U3 and V3 while maintaining the equations. Because it also maintains the values U2 and V2, the algorithm shown in
FIG. 1
not only calculates the greatest common divisor of U and V but also calculates the inverse of V modulo U (assuming U is a prime). That is to say, V
−1
where V·V
−1
=1 modulo U. Furthermore, it is noted that the variables U1, V1 and T1 do not need to be maintained because they can be determined from the other variables, for example, U1 can be determined from U2 and U3 by the identity U1=(U3−U2·V)/U. As described below, when U is a prime number, this inverse may be used for division operations performed on the Finite field F
U
.
The algorithm shown in
FIG. 1
begins at step
110
by obtaining the values U and V. Next, at step
112
a temporary variable U3 is set equal to U and a temporary variable V3 is set equal to V. Also in step
112
the variable U2 is set to zero and V2 is set one. Next, at step
114
the variable V3 is tested to determine if it is equal to zero. When V3 is equal to zero, U3 contains the GCD of U and V and U2 contains the arithmetic inverse of V modulo U (a prime). At step
116
, the values U3 and U2 are returned.
If V3 does not equal zero at step
114
, step
118
is executed. This step calculates a value Q which is equal to the greatest integer less than or equal to U3/V3. Next, it determines a new value for U3 by storing the quantity, U3−Q·V3 into a temporary variable T3. Also at step
118
, the process stores the value U2−Q·V2 into a temporary variable T2. This value is the new value for the variable U2. The variable T3 holds the new value of U3. Because U3 has been reduced but V3 has not, U3 is less than V3. Consequently, the values of U3 and V3 are switched and the values U2 and V2 are also switched by the instructions that set U3=V3, V3=T3, U2=V2 and V2=T2. After step
118
, control returns to step
114
where V3 is once again compared to determine if it is equal to zero. When V3 is equal to zero the process returns the values U3 and U2. The value U3 is the greatest common divisor of U and V while the value U2 is the inverse of V modulo U (i.e. V
−1
MOD U), when U is a prime.
Because the Euclidean algorithm calculates the greatest integer less than
Hars Laszlo
Perkins Gregory Michael
Mai Tan V.
Matsushita Electric - Industrial Co., Ltd.
RatnerPrestia
LandOfFree
Method for calculating arithmetic inverse over finite fields... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for calculating arithmetic inverse over finite fields..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for calculating arithmetic inverse over finite fields... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3201014