Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-04-01
2001-02-06
Mai, Tan V. (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06185596
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to apparatus and methods for modular multiplication and exponentiation and for serial integer division.
BACKGROUND OF THE INVENTION
A compact microelectronic device for performing modular multiplication and exponentiation over large numbers is described in Applicant's U.S. Pat. No. 5,513,133, the disclosure of which is hereby incorporated by reference.
The disclosures of all publications mentioned in the specification and of the publications cited therein are hereby incorporated by reference.
SUMMARY OF THE INVENTION
The present invention seeks to provide improved apparatus and methods for modular multiplication and exponentiation and for serial integer division.
There is thus provided, in accordance with a preferred embodiment of the present invention, a modular multiplication and exponentiation system including a serial-parallel arithmetic logic unit (ALU) including a single multiplier including a single carry-save adder and preferably including a serial division device operative to receive a dividend of any bit length and a divisor of any bit length and to compute a quotient and a remainder.
Further in accordance with a preferred embodiment of the present invention, the system is operative to multiply at least one pair of integer inputs of any bit length.
Still further in accordance with a preferred embodiment of the present invention, the at least one pair of integer inputs includes two pairs of integer inputs.
Additionally in accordance with a preferred embodiment of the present invention, the ALU is operative to generate a product of integer inputs and to reduce the size of the product without previously computing a zero-forcing Montgomery constant, J
0
.
Also provided, in accordance with another preferred embodiment of the present invention, is serial integer division apparatus including a serial division device operative to receive a dividend of any bit length and a divisor of any bit length and to compute a quotient and a remainder.
Further in accordance with a preferred embodiment of the present invention, the apparatus includes a pair of registers for storing a pair of integer inputs and which is operative to multiply a pair of integer inputs, at least one of which exceeds the bit length of its respective register, without interleaving.
Also provided, in accordance with yet another preferred embodiment of the present invention, is a modular multiplication and exponentiation system including a serial-parallel multiplying device having only one carry-save accumulator and being operative to perform a pair of multiplications and to sum results thereof.
Additionally provided, in accordance with still another preferred embodiment of the present invention, is a modular multiplication and exponentiation method including providing a serial-parallel arithmetic logic unit (ALU) including a single modular multiplying device having a single carry-save adder, and employing the serial-parallel ALU to perform modular multiplication and exponentiation.
Further provided, in accordance with yet another preferred embodiment of the present invention, is a method for natural (not modular) multiplication of large integers, the method including providing a serial-parallel arithmetic logic unit (ALU) including a single modular multiplying device having a single carry-save adder, and employing the serial-parallel ALU to perform natural (not modular) multiplication of large integers.
Further in accordance with a preferred embodiment of the present invention, the employing step includes multiplying a first integer of any bit length by a second integer of any bit length to obtain a first product, multiplying a third integer of any bit length by a fourth integer of any bit length to obtain a second product, and summing the first and second products with a fifth integer of any bit length to obtain a sum.
Still further in accordance with a preferred embodiment of the present invention, the employing step includes performing modular multiplication and exponentiation with a multiplicand, multiplier and modulus of any bit length.
Additionally in accordance with a preferred embodiment of the present invention, the system also includes a double multiplicand precomputing system for executing Montgomery modular multiplication with only one precomputed constant.
Further in accordance with yet another preferred embodiment of the present invention, is the employing step includes performing Montgomery multiplication including generating a product of integer inputs including a multiplier and a multiplicand, and executing modular reduction without previously computing a Montgomery constant J
0
.
Further in accordance with a preferred embodiment of the present invention, the Montgomery constant J
0
includes a function of N mod 2
k
, where N is a modulus of the modular reduction and k is the bit-length of the multiplicand.
Still further in accordance with a preferred embodiment of the present invention, the employing step includes performing a sequence of interleaved Montgomery multiplication operations.
Additionally in accordance with a preferred embodiment of the present invention, each of the interleaved Montgomery multiplication operations is performed without previously computing the number of times the modulus must be summated into a congruence of the multiplication operation in order to force a result with at least k significant zeros.
Still further in accordance with a preferred embodiment of the present invention, the system also includes a data preprocessor operative to collect and serially summate multiplicands generated in an i'th interleaved Montgomery multiplication operation thereby to generate a sum and to feed in the sum to an (i+1)'th Montgomery multiplication operation.
Additionally in accordance with a preferred embodiment of the present invention, the function includes an additive inverse of a multiplicative inverse of N mod 2
k
.
Further in accordance with a preferred embodiment of the present invention, the method also comprises computing J
0
by resetting A
i
and B to zero and setting S
0
=1.
The present invention also relates to a compact microelectronic arithmetic logic unit, ALU, for performing modular and normal (natural, non-negative field of integers) multiplication, division, addition, subtraction and exponentiation over very large integers. When referring to modular multiplication and squaring using Montgomery methods, reference is made to the specific parts of the device as a modular arithmetic coprocessor, and the acronym, MAP, is used. Reference is also made to the Montgomery multiplication methods as MM.
The present invention also relates to arithmetic processing of large integers. These large numbers can be in the natural field of (non-negative) integers or in the Galois field of prime numbers, GF(p), and also of composite prime moduli. More specifically, the invention relates to a device that can implement modular multiplications/exponentiations of large numbers, which is suitable for performing the operations essential to Public Key Cryptographic authentication and encryption protocols, which work over increasingly large operands and which cannot be executed efficiently with present generation modular arithmetic coprocessers, and cannot be executed securely with software implementations. The invention can be driven by any 4 bit or longer processor, achieving speeds which can surpass present day digital signal processors.
The present invention also relates to the hardware implementation of large operand integer arithmetic, especially as concerns the numerical manipulations in a derivative of a procedure known as the interleaved Montgomery multiprecision modular multiplication method often used in encryption software oriented systems, but also of intrinsic value in basic arithmetic operations on long operand integers; in particular, A·B+C·D+S, wherein there is no theoretical limit on the sizes of A, B, C, D, or S. In addition, the device is especially attuned to perform modular multip
Arazi Benjamin
Dror Itai
Gressel Carmi David
Hadad Isaac
Fortress U&T Ltd.
Mai Tan V.
Merchant & Gould P.C.
LandOfFree
Apparatus & method for modular multiplication &... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus & method for modular multiplication &..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus & method for modular multiplication &... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2562317