US 2004/0167952 A1 · Method and apparatus for carrying out efficiently arithmetic computations in hardware

Abstract

A method for carrying out modular arithmetic computations involving multiplication operations by utilizing a non-reduced and extended Montgomery multiplication between a first A and a second B integer values, in which the number of iterations required is greater than the number of bits n of an odd modulo value N. The method comprises storing n+2 bit values in an accumulating device (S) capable of, of adding n+2 bit values (X) to it content, and of dividing its content by 2. Whenever desired, the content of the accumulating device is set to zero value. At least s(>n+1) iterations of the following steps are performed, while in each iteration choosing one bit, in sequence, from the value of said first integer value A, starting from its least significant bit: adding to the content of the accumulating device S the product of the selected bit and said second integer value B; adding to the resulting content the product of its current least significant bit and N; dividing the result by 2; and obtaining a non-reduced and extended Montgomery multiplication result by repeating these steps s−1 additional times while in each time using the previous result (S).

Claims23

Dependent claims

a) providing an accumulating device (S) capable of storing n+2 bit values, of adding n+2-bit values (X) to it content (S+X→S), and of dividing its content by 2 (S/2→S);
b) whenever desired, setting the content of said device to a zero value (“0”→S) and performing in said device at least s(>n+1) iterations, while in each iteration choosing one bit, in sequence, from the value of said first integer value A (AI;
0≦I≦s−1), starting from its least significant bit (A0):
b.1) adding to the content of said device S the product of the selected bit AI and said second integer value B (S+AI*B→S);
b.2) adding to the resulting content of said device the product of its current least significant bit S0 and N(S+S0*N→S);
b.3) dividing the resulting content of said device by 2 (S/2→S);
and
b.4) obtaining a non-reduced and extended Montgomery multiplication:
result by repeating steps b.1) to b.3) s−1 additional times while in each time using the previous result (S).

6 more elements

Apparatus for carrying out extended and non-reduced Montgomery multiplication of a first (A) and second (B) integer values, in which the number of iterations (s) required is greater the number of bits (n) in the modulo value (N), and in which the Montgomery multiplication result is smaller than twice the modulo value (2×N), comprising:

a) a first storage device (R2) for storing the modulo value (N);
b) a second storage device (R0) for storing the value of said first integer values (A);
c) a third storage device (R1) for storing the sum of said first integer value and said modulo (A+M);
d) an arbitration circuitry having a first (In1), second (In2) and third (In3), inputs from said first (R2), second (R0), and third (R1), storage devices, and having a fourth input which is zero (“0”), said arbitration device receives a first (C1) and a second (C0) control inputs, and thereby is capable of selecting one of it other inputs as it output, that is attached to the input of the accumulating device;
e) circuitry for producing the state (K1) of said second control input (C0) according to the state of a selected bit of said first integer value (A1), the state of the least significant bit of said second integer value (B0), and according to the state of the least significant bit of said accumulating device (S0);
and
f) an accumulating device (S) capable of storing n+2 bits values, of adding n+2-bits values (X) to it content (S+X→S), and of dividing it content by 2 (S/2→S).

4 more elements

Dependencies are inferred from the claim text.

Method and apparatus for carrying out efficiently arithmetic computations in hardware

Life of this patent

Method and apparatus for carrying out efficiently arithmetic computations in hardware

Life of this patent

Abstract

Claims23