Method and apparatus for multiplication and/or modular reduction processing

1. Automatic computing machinery having logic embodied thereon for performing a method of modular reduction processing of a number which is represented by a sequence of digits, comprising:

providing a modular reduction processor;

receiving a number x, wherein number x is provided in radix b form and is represented by sequence of 2k digits such that {x i |i=0, 1, 2, . . . , 2k−1}; and

processing x, via the modular reduction processor, wherein x is processed least significant digit first and in digits in increasing order of significance thereafter, wherein processing x comprises:

dividing x by b k+1 to produce q 1 ;

multiplying q 1 by μ to produce q 2 , wherein μ is given in radix b form and is represented by sequence of k+1 digits such that μ=└b 2k /m┘, wherein m is modulus given in radix b form and is represented by sequence of k digits such that {m i |i=0, 1, 2, . . . , 2k−1} wherein m k−1 ≠0);

dividing q 2 by b k+1 to produce q 3 ;

multiplying q 3 by m;

reducing the product of q 3 multiplied by m modulo b k+1 to produce r 2 ;

reducing x modulo b k+1 to produce r 1 ;

subtracting r 2 from r 1 to produce r; and

determining which of the following is true:

r is non-negative and r a1 is negative, wherein r a1 is r−m;

r is non-negative and r a1 is non-negative and r a2 is negative, wherein r a2 is r−2m;

r is non-negative and r a2 is non-negative;

r is negative and r pa1 is negative, wherein r pa1 =r+b k+1 −m;

r is negative and r pa1 is non-negative and r pa2 is negative, wherein r pa2 =r+b k+1 −2m; and

r is negative and r pa2 is non-negative,

wherein if r is non-negative and r a1 is negative, x mod m=r,

wherein if r is non-negative and r a1 is non-negative and r a2 is negative, x mod m=r−m,

wherein if r is non-negative and r a2 is non-negative, x mod m=r−2m,

wherein if r is negative and r pa1 is negative, x mod m=r+b k+1 ,

wherein if r is negative and r pa1 is non-negative and r pa2 is negative, x mod m=r+b k+1 −m, and

wherein if r is negative and r pa2 is non-negative, x mod m=r+b k+1 −2m.

2. The automatic computing machinery according to claim 1 , wherein x is received least significant digit first and in digits in increasing order of significance thereafter.

3. The automatic computing machinery according to claim 1 , wherein b is a power of 2.

4. The automatic computing machinery according to claim 3 , wherein dividing x by b k−1 comprise removing the k−1 least significant digits from x.

5. The automatic computing machinery according to claim 1 , wherein reducing the product of q 3 multiplied by m modulo b k+1 to produce r 2 comprises taking the k+1 least significant digits of q 3 m mod b k+1 .

6. The automatic computing machinery according to claim 1 , wherein subtracting r 2 from r 1 to produce r comprises sequentially subtracting r 2 from r 1 to produce r.

7. The automatic computing machinery according to claim 1 ,

wherein the number x is received and processed sequentially, one radix b digit at a time, wherein the modular reduction processor is a sequential modular reduction processor.

8. The automatic computing machinery of claim 1 , the method further comprising:

providing a shift-and-truncate down operator and a sequential multiplier, wherein:

dividing x by b k+1 is performed via the shift-and-truncate down operator; and

multiplying q 1 by μ is performed via the sequential multiplier.

9. Automatic computing machinery having logic embodied thereon for performing a method of sequential multiplication for multiplying two numbers, each number having no more than kN bits, comprising:

a. receiving a first number a, wherein a is represented by a sequence of k digits such that {a i |i=0, 1, 2, . . . , k−1} and each a i is a radix b digit having N bits;

b. receiving a second number c, wherein c is represented by a sequence of k digits such that {c i |i=0, 1, 2, . . . , k−1} and each c i is a radix b digit having N bit;

c. producing a sum y=Σ i=0 2k−2 y′ i b i , wherein y′ i =Σ j=0 i a j c i−j , such that y′ i can be represented as a sequence of 2k−1 digits such that {y′ i |i=0, 1, 2, . . . , 2k−2}, wherein y is the product of a and c and can be represented by a sequence of 2k digits such that {y i |i=0, 1, 2, . . . , 2k−1} and each y i is a radix b digit having N bits.

10. The automatic computing machinery according to claim 9 , wherein producing the sum y comprises:

a. inputting a least significant digit of a into a first register of a shift register;

b. inputting a least significant digit of c into first register of a register file and setting the remaining registers of the register file to zero;

c. multiplying a value of each register of the shift register by a value of a corresponding register of the register file and adding the products to produce a first sum;

d. selecting the least significant N bits of the first sum as the least significant N bits of a product of a and c;

e. selecting the most significant N+└ log 2k┘=1 bits of the first sum and saving the most significant N+└ log 2k┘+1 bits of the first sum in a carry register;

f. inputting the next least significant digit of a into the first register of the shift register and shifting the shift register values;

g. inputting the next least significant digit of c into the next register of the register file;

h. multiplying the value of each register of the shift register by the value of a corresponding register of the register file and adding the products to produce a next first sum;

i. adding the first sum to the value of the carry register to produce a second sum;

j. selecting the least significant N bits of the second sum as the next least significant N bits of a product of a and c;

k. selecting the most significant N+└ log 2k┘=1 bits of the second sum and saving the most significant N+└ log 2k┘+1 bits of the second sum in the carry register;

l. inputting the next least significant digit of a into the first register of the shift register and shifting the shift register values;

m. inputting the next least significant digit of c into the next register of the register file;

n. multiplying the value of each register of the shift register by the value of the corresponding register of the register file and adding the products to produce a next first sum;

o. adding the next first sum to the value of the carry register to produce a next second sum;

p. selecting the least significant N bits of the next second sum as the next least significant N bits of the product of a and c;

q. selecting the most significant N+└ log 2k┘+1 bits of the next second sum and saving the most significant N+└ log 2k┘+1 bits of the next second sum in the carry register;

r. repeating steps j through o k−3 times;

s. inputting a zero into the first register of the shift register and shifting the shift register values;

t. multiplying the value of each register of the shift register by the value of the corresponding register file and adding the products to produce a next first sum;

u. adding the next first sum to the value of the carry register to produce a next second sum;

v. selecting the least significant N bits of the next second sum as the next least significant N bits of the product of a and c;

w. selecting the most significant N+└ log 2k┘+1 bits of the next second sum in the carry register;

x. repeating steps s through w k−1 times; and

y. selecting the value in the carry register as the most significant N bits of the product of a and c.

11. Automatic computing machinery having logic embodied thereon for performing a method of modular reduction processing of a product of two numbers, comprising:

receiving a first number a, wherein a is provided in radix b form and is represented by a sequence of k digits such that {a i |i=0, 1, 2, . . . , k−1};

receiving a second number c, wherein c is provided in radix b form and is represented by a sequence of k digits such that {c i |i=0, 1, 2, . . . ,k−1};

multiplying the first number and the second number to produce a product which is represented by a sequence of 2k digits;

inputting the product into a modular reduction processor, wherein the modular reduction processor outputs one or more of the following:

r, r−m, r−2m, r+b k+1 , r+b k+1 −m, and r+b k+1 −2m, wherein r=x mod b k+1 −m[[μ(x/b k−1 )]/b k+1 ]mod b k+1 , into a means for determining which of the following is true:

r is non-negative and r a1 is negative, wherein r a1 is r−m;

r is non-negative and r a1 is non-negative and r a2 is negative, wherein r a2 is r−2m;

r is non-negative and r a2 is non-negative;

r is negative and r pa1 is negative, wherein r pa1 =r+b k+1 −m;

r is negative and r pa1 is non-negative and r pa2 is negative, wherein r pa2 =r+b k+1 −2m; and

r is negative and r pa2 is non-negative,

wherein if r is non-negative and r a1 is negative, x mod m=r,

wherein if r is non-negative and r a1 is non-negative and r a2 is negative, x mod m=r−m,

wherein if r is non-negative and r a2 is non-negative, x mod m=r−2m,

wherein if r is negative and r pa1 is negative, x mod m=r+b k+1 ,

wherein if r is negative and r pa1 is non-negative and r pa2 is negative, x mod m=r+b k+1 −m, and

wherein if r is negative and r pa2 is non-negative, x mod m=r+b k+1 −2m.

12. An apparatus for modular reduction processing of a number which is represented by a sequence of digits, comprising:

a means for receiving a number x, wherein number x is provided in radix b form and is represented by sequence of 2k digits such that {x i |= 0, 1, 2, . . . , 2k−1};

a means for processing x, wherein x is processed least significant digit first and in digits in increasing order of significance thereafter, wherein the means for processing x comprises:

a means for dividing x by b k−1 produce q i ;

a means for multiplying q 1 , by μ to produce q 2 , wherein μ is given in radix b form and is represented by sequence of k+1 digits such that μ=└b 2k/m ┘, wherein m is modulus given in radix b form and is represented by sequence of k digits such that {m 1 |=0, 1, 2, . . . , 2k−1} wherein m k−1 ≠0);

a means for dividing q 2 by b k+1 to produce q 3 ;

a means for multiplying q 3 by m;

a means for reducing the product of q 3 multiplied by m modulo b k+1 to produce r 2 ;

a means for reducing x modulo b k+1 to produce r 1 ;

a means for subtracting r 2 from r 1 to produce r; and

a means for determining which of the following is true:

r is non-negative and r a1 is negative, wherein r a1 is r−m;

r is non-negative and r a1 is non-negative and r a2 is negative, wherein r a2 is r−2m;

r is non-negative and r a2 is non-negative;

r is negative and r pa1 is negative, wherein r pa1 =r+b k+1 −m; and

r is negative and r pa1 is non-negative and r pa2 is negative, wherein r pa2 =y+b k+ −2m; and

r is negative and r pa2 is non-negative,

wherein if r is non-negative and r a1 is negative, x mod m=r,

wherein if r is non-negative and r a1 is non-negative and r a2 is negative, x mod m=r−m,

wherein if r is non-negative and r a2 non-negative, x mod m=r−2m,

wherein if r is negative and r pa1 is negative, x mod m=r+b k+1 ,

wherein if r is negative and r pa1 is non-negative and r pa2 is negative, x mod m=r+b k−1 −m, and

wherein if r is negative and r pa1 is non-negative, x mod m=r+b k+1 −2m.

13. The apparatus according to claim 12 , wherein x is received least significant digit first and in digits in increasing order of significance thereafter.

14. The apparatus according to claim 12 , wherein b is a power of 2.

15. The apparatus according to claim 14 , wherein a means for dividing x by b k−1 comprises removing the k−1 least significant digits from x.

16. The apparatus according to claim 12 , wherein a means for reducing the product of q 3 multiplied by m modulo b k+1 to produce r 2 comprises a means for taking the k+1 least significant digits of q 3 m mod b k+1 .

17. The apparatus according to claim 12 , wherein a means for subtracting r 2 from r 1 to produce r comprises sequentially subtracting r 2 from r 1 to produce r.

18. An apparatus for sequential multiplication for multiplying two numbers, each number having no more than kN bits, comprising:

a. a means for receiving a first number a, wherein a is represented by a sequence of k digits such that {a i |i=0, 1, 2, . . . , k−1} and each a i is a radix b digit having N bits;

b. a means for receiving a second number c, wherein c is represented by a sequence of k digits such that {c i |i=0, 1, 2, . . . , k−1} and each c i is a radix b digit having N bit;

c. a means for producing a sum y=Σ i=0 2k−2 wherein y i ′=Σ j−0 i a j c i−j , such that y i ′ can be represented as a sequence of 2k−1 digits such that {y i ′|i=0, 1, 2, . . . , 2k−2}, wherein y is the product of a and c and can be represented by a sequence of 2k digits such that {y i |i=0, 1, 2, . . . , 2k−1} and each y i is a radix b digit having N bits.

19. The apparatus according to claim 12 , wherein the number x is received and processed sequentially, one radix b digit at a time.

20. The apparatus according to claim 12 , wherein:

the means for processing x comprises a modular reduction processor;

the means for dividing x by b k+1 comprises a shift-and-truncate down operator; and

the means for multiplying q i by μ comprises a sequential multiplier.

21. An apparatus for modular reduction processing of a product of two numbers, comprising:

a means for receiving a first number a, wherein a is provided in radix b form and is represented by a sequence of k digits such that {a i |i=0, 1, 2, . . . , k−1};

a means for receiving a second number c, wherein c is provided in radix b form and is represented by a sequence of k digits such that {c i |i=0, 1, 2, . . . , k−1};

a means for multiplying the first number and the second number to produce a product which is represented by a sequence of 2k digits;

a means for inputting the product into a modular reduction processor, wherein the modular reduction processor outputs one or more of the following:

r, r−m, r−2m, r+b k+1 , r+b k+1 −m, and r+b k+1 −2m, wherein r=x mod b k+ −m[[μ(x/b k−1 )]/b k+1 ]mod b k+1 , into a means for determining which of the following is true:

r is non-negative and r a1 is negative, wherein r a1 is r−m;

r is non-negative and r a1 is non-negative and r a2 is negative, wherein r a2 is r−2m;

r is non-negative and r a2 is non-negative;

r is negative and r pa1 is negative, wherein r pa1 =r+b k+1 −m;

r is negative and r pal is non-negative and r pa2 is negative, wherein r pa2 =r+b k+1 −2m; and

r is negative and r pa2 is non-negative,

wherein if r is non-negative and r a1 , is negative, x mod m=r,

wherein if r is non-negative and r a1 is non-negative and r a2 is negative, x mod m=r−m,

wherein if r is non-negative and r a2 is non-negative, x mod m=r−2m,

wherein if r is negative and r pa1 is negative, x mod m=r+b k+1 ,

wherein if r is negative and r pa1 is non-negative and r pa2 is negative, x mod m=r+b k+1 −m, and

wherein if r is negative and r pa2 is non-negative, x mod m=r+bhu k+ 1 −2m.