Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-11-09
2001-07-31
Ngo, Ohuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S523000
Reexamination Certificate
active
06269383
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to arithmetic computation involving large integers, and more particularly, to a means for performing multiplication and modular reduction of large integers.
DESCRIPTION OF THE RELEVANT ART
The present invention is motivated by applications of public-key cryptography including the RSA scheme, RSA Laboratories, “The Public-Key Cryptography Standards,” RSA Data Security, Inc., Redwood City, Calif., November 1993; the Diffie-Hellman scheme, W. Diffie and M. Hellman, “New Directions in Cryptography,”
IEEE Transactions on Information Theory,
Vol. IT-22, No. Jun. 6, 1977, pp. 74-84; and the DSA scheme, “Digital Signature Standard,” FIPS Publication 186, National Institute of Standards and Technology, U.S. Department of Commerce, May 18, 1994. These applications require the computational step of modular exponentiation, that is, a computation of the form “A
B
modulo P,” where A, B, and P are large integers. Modular exponentiation is a computationally demanding procedure that can take a long time to perform, especially on inexpensive computing devices.
Computing devices typically are designed to process data in basic units of a fixed size. The basic data unit is called a “word” and comprises “b” bits. The value of b is selected when the device is designed. Typical values for b are 8, 16, 32, or 64 bits. A word is used to represent a non-negative integer x in the range 0≦x≦W−1, where W=2
b
.
To represent an integer X that is larger than W−1, a multiprecision representation is used. If 0≦X≦W
n
−1, where n is some positive integer, then X can be represented as:
X=x{n
−1
}*W
n−1
+x{n
−2
}*W
n−2
. . . +x
{
1
}*
W+x
{
0
},
where each x{j} is in the range 0≦x{j}≦W−1, j=0, 1, . . . , n−1. Thus, the integer X is represented by the n words x{
0
}, x{
1
}, . . . , x{n−1}, with word x{j} representing an integer that is the coefficient of W
j
. For a given word size b, and a given number of words n, the multiprecision representation of X is unique.
Modular exponentiation requires several operations involving multiprecision integers. One such operation is multiplication. Given two integers X and Y, each with a multiprecision representation of n words, it is straightforward to program the computing device to calculate the product Z=X*Y. The procedure is little more than the “multiply and add” method taught in grammar school for multiplying multidigit numbers. The complexity of the procedure is quadratic, that is, the number of “inner products” that must be computed is n
2
. The product Z requires 2n words to represent it.
In practical public key applications, a single modular exponentiation requires hundreds or thousands of such multiplications, each involving integers that are tens or hundreds of words long. On a simple computing device, the computation time for a single exponentiation can be several minutes. For many applications, such as electronic commerce, this is too long to be useful.
Multiplication is not the only operation involved in modular exponentiation. Another operation is modular reduction, that is, the reduction of the product Z from 2n words to n words by applying a “modulo P” operation. The complexity of modular reduction is nearly identical to that of multiplication, and the two contribute nearly equally to the total run time of a modular exponentiation.
SUMMARY OF THE INVENTION
The present invention takes advantage of the observation that both multiprecision multiplication and modular reduction can be rapidly calculated if the computing device has the capability to efficiently carry out the following operation:
Z−Z
±(
X*Y
).
In this operation, X is an integer represented by m words, and Y and Z are each integers represented by n words. The intent is that n is the number of words in the modulus for which the modular exponentiation is being computed, while m is a smaller value than n. Multiprecision multiplication and modular reduction can each be carried out using approximately n/m executions of this operation, for a total of 2n/m operations for the modular exponentiation.
The present invention discloses a coprocessor that can be added to a computing device to enable the computing device to perform this operation efficiently. When instructed by the computing device to do so, the coprocessor performs the operation Z−Z±(X*Y), reading the words of X, Y, and Z from memory, and writing the new words of Z back to memory. The computing device assembles these operations into multiprecision multiplication, modular reduction, and ultimately, modular exponentiation.
The building block for the coprocessor is a large integer unit (LIU). The coprocessor contains one or more LIU's, each identical to each other. Each LIU includes a multiplier, an adder, a register and an OR gate. Multiple LIU's may be connected to form an LIU Array which includes a complementing gate, a latching register, and an output gate. The greater the number of LIU's included in the array, the faster the exponentiation.
Additional objects and advantages of the invention are set forth in part in the description which follows, and in part are obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention also may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
REFERENCES:
patent: 4215617 (1980-08-01), Moorer
patent: 4608634 (1986-08-01), Caudel et al.
patent: 4771379 (1988-09-01), Ando et al.
patent: 5194681 (1993-03-01), Kudo
patent: 5278781 (1994-01-01), Ando et al.
patent: 5280439 (1994-01-01), Quek et al.
patent: 5321751 (1994-06-01), Iwamura et al.
patent: 5457804 (1995-10-01), Ohtomo et al.
patent: 5661673 (1997-08-01), Davis
Heising Mark W.
Sabin Michael J.
Atmel Corporation
David Newman Chartered
Ngo Ohuong Dinh
LandOfFree
Method and apparatus for integer arithmetic 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 and apparatus for integer arithmetic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for integer arithmetic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497764