Efficient greatest common divisor algorithm using...

Details Efficient greatest common divisor algorithm using... Efficient greatest common divisor algorithm using...

2001-01-17

2004-12-28

Malzahn, D. H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S200000, C380S030000

Reexamination Certificate

active

06836784

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention is directed to greatest common divisor algorithms and in particular to such an algorithm that uses multi-precision arithmetic and iteratively reduces the number of bits in each of the values it is testing either by performing an approximate division reduction step or by performing a novel inter-reduction step.
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, the operations of addition, subtraction, multiplication and division 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, Fp.
GCD algorithms are commonly used to screen candidate large prime numbers. If a number passes the GCD test a more rigorous test is applied to determine if the number is prime. As set forth above, large prime number are important because they define Finite fields which are of interest for encryption purposes. One type of encryption algorithm encrypts data using exponentiation, relying on the inherent difficulty of the reverse of exponentiation, the discrete logarithm problem, to hold the data secure. Because encryption performed on a large Finite field is more secure than encryption performed on a small field, these algorithms work best when the exponentiation operations are carried out over a large Finite field. Thus, there is a need to identify large prime numbers. One problem with using large fields, however, is the size of the numbers being processed. 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. As described below, calculations used in the encryption process are typically handled using multiprecision arithmetic.
FIG. 1
is a flow chart diagram of an algorithm that screens candidate prime numbers. The GCD algorithm is relatively quick and can find weed-out many candidate prime numbers having relatively small factors. The algorithm shown in
FIG. 1
tests a number P to determine if it is prime relative to the first N thousand prime numbers where N is an integer. Prior to performing the algorithm shown in
FIG. 1
, an array THOUSAND_PRIMES [I] is prepared such that THOUSAND_PRIMES [
1
] contains the product of the first thousand prime numbers, THOUSAND_PRIMES [
2
] contains the product of the second thousand prime numbers and so on. The process begins at step
102
by obtaining the number P which is to be tested and the number N defining the number of thousand primes that P is to be tested against. At step
104
an index variable I is set to zero. At step
106
, I is incremented by one and a value G is calculated where G is the greatest common divisor of P and THOUSAND_ PRIMES [I]. If, at step
108
, G is greater than one then P is divisible by one of the factors of THOUSAND_PRIMES [I] and is not prime. Accordingly, control transfers to step
110
where the value FALSE is returned.
If, however, at step
108
G is equal to one then P is not divisible by any of the factors of THOUSAND_PRIMES [I] and control transfers to step
112
. At step
112
the variable I is compared against N. If I is less than N control transfers to step
106
where I is incremented and the greatest common divisor of P and THOUSAND_PRIMES [I] is calculated for the incremented value of I. When, at step
112
, I is equal to N, the number P has been tested against the N thousand prime numbers and has been found to be relatively prime to each of these products. Thus, at step
114
, the algorithm shown in
FIG. 1
returns a value TRUE indicating that P is a good candidate to be a prime number. After performing the test shown in
FIG. 1
, the candidate prime number may be processed using a probabilistic primality testing routine, such as the Miller-Rabin algorithm to determine if it is prime.
A key element of the program shown in
FIG. 1
is the greatest common divisor (GCD) algorithm.
FIG. 2
is a flow chart diagram which illustrates a greatest common divisor algorithm known as Euclid's algorithm. The algorithm shown in
FIG. 2
calculates the greatest common divisor of U and V where U is greater than V. The algorithm shown in
FIG. 2
also calculates the inverse of V modulo U. This algorithm relies on the property that if U and V have a common divisor D so does U-V, U-
2
V 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. When calculating the inverse, The GCD algorithm operates by maintaining the linear equations (1), (2) and (3)
U
1
P+U
2
X=U
3
  (1)
V
1
P+V
2
X=V
3
  (2)
T
1
P+T
2
X=T
3
  (3)
Where U≧V and U
3
and V
3
are initially assigned the values of U and V, respectively. Upon termination, U
3
=GCD(P, X)=1 and U
2
=X
−1
MOD P. In general terms, GCD algorithms operate by repetitively reducing the number of bits in the larger value, U
3
, and switching the two values U
3
and V
3
. Thus, the algorithm successively reduces the values of U
3
and V
3
while maintaining the linear equations. Because it maintains the values U
2
and V
2
, the algorithm shown in
FIG. 2
not only calculates the greatest common divisor of U and V but also calculates the inverse of V modulo U. That is to say, V
−1
where V*V
−1
=1 modulo U. As described below, when U is a prime number, this inverse may be used to simplify division calculations performed within the Finite fields Fu. Furthermore, the variables U
1
, V
1
and T
1
do not need to be maintained because they can be determined from the other variables, for example, U
1
can be determined from U
2
and U
3
by the identity U
1
=(U
3
−U
2
V)/U.
The Euclid GCD algorithm shown in
FIG. 2
begins at step
210
by obtaining the values U and V. Next, at step
212
a temporary variable U
3
is set equal to U and a temporary variable V
3
is set equal to V. Also in step
212
variable U
2
is set to zero and V
2
is set one. Next, at step
214
the variable V
3
is tested to determine if it is equal to zero. If not, step
218
is executed. This step calculates a value Q which is equal to the greatest integer less than U
3
/V
3
. Next, it determines a new value for V
3
by storing the quantity, U
3
−Q*V
3
into a temporary variable T
3
. Also at step
218
, the process stores the value U
2
−Q*V
2
into a temporary variable T
2
. This value is the new value for the variable V
2
. The value in T
3
represents a reduced value of U
3
. Because V
3
has not been reduced, however, T
3
is less than V
3
. Consequently, the value in V
3
is assigned to U
3
and the value in T
3
is assigned to V
3
. A similar operation is performed on the variables U
2
, V
2
and T
2
. After step
218
, control returns to step
214
where V
3
is once again compared to determine if it is equal to zero. When V
3
is equal to zero the process returns the values U
3
and U
2
. The value U
3
is the greatest common divisor of U and V while the value U
2
is the inverse of V modulo U (i.e. V
−1
MOD U).
As described above, a modular arithmetic operation that is used in many encryption algorithms is raising a large number M, representing a message, to a power E modulo P. In a typical encryption example the values M, E and P are each hundreds of bits in length. Operations on numbers of this size—and especially division operations—are difficult because common computer processing hardware supports at most sixty-four bit mathematical operations. Values greater than 64 bits in length are typically calculated using multiprecision arithmetic. A number, a, raised to an exponent e can always be calculated by multiplying that number by itself the number of time represented by the ex

Affiliated with

Also associated with

Rating

Efficient greatest common divisor algorithm using... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient greatest common divisor algorithm using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient greatest common divisor algorithm using... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3295657