High-speed modular multiplication apparatus achieved in small circuit
First Claim
1. A modular multiplication apparatus for calculating a congruent value of a modulo P multiplication of a product of a multiplicand a and a kb-bit multiplier b, wherein P is k-bit, the congruent value being obtained from a following formula:
-
where [[kb/s]] represents integers included in quotient kb/s, i represents integers in a range of 0 to [[kb/s]], C(i) is represented by a recurrence formula, and C(i)=a (i=0) C(i)=(C(i−
1)*2s) mod P (i≧
1) C(i) (intermediate value) is a congruent value of a modulo P multiplication of a product (a preceding intermediate value*2s), wherein the congruent value is calculated recurrently, an initial intermediate value is the multiplicand a, and the product being equal to the preceding intermediate value shifted s bits, b[s*i+s−
1;
s*i] represents s-bit partial multipliers included in the multiplier b at places from 2s*i+s−
1 to 2s*i, the modular multiplication apparatus comprising;
a table means which prestores residues of modulo p multiplications of (m-bit value)*2k, wherein m is an integer s or larger;
an intermediate value calculation means for outputting the multiplicand a as an intermediate value C(0) first time (i=0) and second time and after (i≧
1), performing a shift of s bits on a preceding intermediate value C(i−
1) to acquire a shifted intermediate value, referring to the table means to read out a residue corresponding to in bits adjacent to lower k bits of the shifted intermediate value, and obtaining another intermediate value C(i) by adding up the read-out residue and the lower k bits; and
an accumulation means for obtaining the accumulated value by detecting, in order from lower bits, partial multipliers b[s*i+s−
1;
s*i] which are s-bit parts making up the multiplier b, calculating a partial product C(i)*b[s*i+s−
1;
s*i] for each of the first time (i=0) through the last time (i=[[kb/s]], and accumulating the calculated partial products.
1 Assignment
0 Petitions
Accused Products
Abstract
The modular multiplication apparatus includes a residue calculating unit, a multiplier division unit, a partial product calculation unit, an accumulation unit, a correction unit, and a control unit. The residue calculating unit recurrently calculates intermediate values in sequence. The residue calculating unit obtains the multiplicand as the intermediate value first time, and at the second time and after, calculates residues or congruent values of the modulo P multiplication of the intermediate values being preceding intermediate values left-shifted s bits. The multiplier division unit divides the multiplier into a plurality of s-bit partial multipliers in order from lower bits. The partial product calculation unit calculates partial products of intermediate values and partial multipliers in sequence. The accumulation unit and the correction unit accumulate the partial products while correcting them under the control of the control unit. The residue calculating unit includes a table unit. The table unit prestores residues of modulo p multiplications of (m-bit value) *2k, where the m-bit values respectively correspond to values from decimal values 0 to 2m−1. The residue calculating unit refers to the table unit to read out a residue corresponding to higher m bits adjacent to the lower k bits of the left-shifted intermediate value. The residue calculating unit calculates a residue or a congruent value of modulo p multiplications of the left-shifted intermediate value by adding up the read-out residue and the lower k bits.
27 Citations
79 Claims
-
1. A modular multiplication apparatus for calculating a congruent value of a modulo P multiplication of a product of a multiplicand a and a kb-bit multiplier b, wherein P is k-bit, the congruent value being obtained from a following formula:
-
where [[kb/s]] represents integers included in quotient kb/s, i represents integers in a range of 0 to [[kb/s]], C(i) is represented by a recurrence formula, and C(i)=a (i=0) C(i)=(C(i−
1)*2s) mod P (i≧
1)C(i) (intermediate value) is a congruent value of a modulo P multiplication of a product (a preceding intermediate value*2s), wherein the congruent value is calculated recurrently, an initial intermediate value is the multiplicand a, and the product being equal to the preceding intermediate value shifted s bits, b[s*i+s−
1;
s*i] represents s-bit partial multipliers included in the multiplier b at places from 2s*i+s−
1 to 2s*i, the modular multiplication apparatus comprising;
a table means which prestores residues of modulo p multiplications of (m-bit value)*2k, wherein m is an integer s or larger;
an intermediate value calculation means for outputting the multiplicand a as an intermediate value C(0) first time (i=0) and second time and after (i≧
1), performing a shift of s bits on a preceding intermediate value C(i−
1) to acquire a shifted intermediate value, referring to the table means to read out a residue corresponding to in bits adjacent to lower k bits of the shifted intermediate value, and obtaining another intermediate value C(i) by adding up the read-out residue and the lower k bits; and
an accumulation means for obtaining the accumulated value by detecting, in order from lower bits, partial multipliers b[s*i+s−
1;
s*i] which are s-bit parts making up the multiplier b, calculating a partial product C(i)*b[s*i+s−
1;
s*i] for each of the first time (i=0) through the last time (i=[[kb/s]], and accumulating the calculated partial products.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
the intermediate value calculation means includes: a first hold means for holding an intermediate value;
a shift means -for obtaining the shifted intermediate value by performing a shift of s bits on the intermediate value held by the first hold means in correspondence to the partial multiplier b[s*i+s−
1;
s*i];
a division means for dividing the shifted intermediate value into a higher data and a lower data, wherein the higher data is composed of m bits adjacent to lower k bits of the shifted intermediate value, and the lower data is composed of the lower k bits;
a read means for referring to the table means to read out a residue corresponding to the higher data; and
an addition means for calculating another intermediate value by adding up the read-out residue and the lower data, wherein the first hold means updates the intermediate value to the other intermediate value calculated by the addition means each time the addition means calculates a new intermediate value, and outputs the multiplicand as an intermediate value first time, and outputs the updated intermediate Value second time and after.
-
-
3. The modular multiplication apparatus of claim 2, wherein
the table means includes: a memory device which prestores residues of modulo p multiplications of (m-bit value)*2k, wherein storage areas of residues respectively correspond to addresses to be input, and the addresses further correspond to m-bit values.
-
4. The modular multiplication apparatus of claim 2, wherein
the m-bit value is divided into an m1-bit value and an m2-bit value, where the m1-bit value is composed of lower m1 bits and the m2-bit value is composed of higher m2 bits, wherein m=m1+m2, each m-bit value corresponds to a combination of an m1-bit value and an m2-bit value, the table means includes: -
a first Part table means which prestores residues of modulo p multiplications of (m1-bit value)*2k; and
a second part table means which prestores residues of modulo p multiplications of (m2-bit value)*2k+m1, wherein the addition means adds up residues respectively read out from the first part table means, and the second part table means and the lower data.
-
-
5. The modular multiplication apparatus of claim 2, wherein
the m bits are divided into t bit-sequences respectively having m1 bits, m2 bits, . . . mt bits in order from lower bits, wherein 3≦ - t≦
m,the m bits are divided into t bit-sequences which respectively have m1 bits, m2 bits, . . mt bits, wherein 3≦
t≦
m,each m-bit value corresponds to a combination of values respectively represented by t bit-sequences mi, wherein i represents each integer in a range of 1 to t, the table means includes;
t partial table means Ti which each prestore residues of modulo p multiplications of (mi-bit value)*2k+x, wherein x=m1+m2+ . . . +m(i−
1), andthe addition means adds up t residues respectively read out by the read means from the t partial table means Ti and the lower data.
- t≦
-
6. The modular multiplication apparatus of claim 2, wherein
the m bits are divided into t bit-sequences respectively having m1 bits, m2 bits, . . . mt bits in order from, lower bits, wherein 2≦ - t≦
m,the table means includes;
t partial table means Ti which each prestore residues of modulo p multiplications of (a value represented by bit-sequences mi)*2k+x, wherein the addition means adds up t residues respectively read out by the read means from the t partial table means Ti and the lower data, wherein a result of this addition is equivalent to the other intermediate value.
- t≦
-
7. The modular multiplication apparatus of claim 6, wherein
each of the t partial table means Ti prestores each of the residues as k-bit data. -
8. The modular multiplication apparatus of claim 7 further comprising:
- an accumulation means; and
a correction means, whereinthe accumulation means includes;
a third register for holding 0 as an initial value; and
an adder for adding up the partial products C(i)*b[s*i+s−
1;
s*i] and the accumulated value stored in the third register and storing a result of this addition into the third register as another accumulated value, whereinthe correction means includes;
a correction value hold means for holding a correction value being an integral multiple of P; and
a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
- an accumulation means; and
-
9. The modular multiplication apparatus of claim 8, wherein
the third register includes a sign bit, the correction control means allows the adder to subtract the correct ion value from the accumulated value at the same time when the adder adds up the partial product and the accumulated value stored in the third register when the accumulated value is positive, and the correction value is an integral multiple of 1 and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1)(2s− - 1) P of the partial product.
-
10. The modular multiplication apparatus of claim 6, wherein
the modulo P multiplication satisfies P=2k− - α
,each of the t partial table means Ti prestores each of the residues as k3-bit data, wherein k3 is equivalent to the number of bits in t*2m*α
, and α
is a constant defined to satisfy a condition that k3 is smaller than k.
- α
-
11. The modular multiplication apparatus of claim 10, wherein
each of the t partial table means Ti includes 2mi entries which respectively correspond to values in a range of 0 to (2mi− - 1) each having mi bits, wherein
the jth entry stores (j−
1)*2m1+ . . . +m(i−
1)*α
, wherein j=1, . . . 2mi.
- 1) each having mi bits, wherein
-
12. The modular Multiplication apparatus of claim 11 further comprising:
- an accumulation means; and
a correction means, whereinthe accumulation means includes;
a third register for holding 0 as an initial value; and
an adder for adding up the partial products C(i)*b[s*i+s−
1;
s*i] and the accumulated value stored in the third register and storing a result of this addition into the third register as another accumulated value, whereinthe correction means includes;
a correction value hold means for holding a correction value being an integral multiple of P; and
,a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
- an accumulation means; and
-
13. The modular multiplication apparatus of claim 12, wherein
the third register includes a sign bit, the correction control means allows the adder to subtract the correction value from the accumulated value at the same time when the adder adds up the partial product and the accumulated value stored in the third register when the accumulated value is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (2s+1*t− - 2) P of the partial product.
-
14. The modular multiplication apparatus of claim 2 further comprising:
a post-processing means for using the table means to obtain a residue of a modulo P multiplication of a last accumulated value having been corrected by the correction means, wherein the last accumulated value is an accumulated value corrected by the correction means in correspondence to a partial multiplier including the most significant bit of the multiplier.
-
15. The modular multiplication apparatus of claim 14, wherein
the table means includes: a memory device which prestores residues of modulo p multiplications of (m-bit value)*2k, wherein storage areas of residues respectively correspond to addresses to be input, and the addresses further correspond to m-bit values.
-
16. The modular multiplication apparatus of claim 14, wherein
the m bits are divided into lower m1 bits and higher m2 bits, wherein m=m1+m2, each m-bit values corresponds to a combination of an m1-bit value and an m2-bit value, the table means includes: -
a first part table means which prestores residues of modulo p multiplications of (m1-bit value)*2k+m1, and a second part table means which prestores residues of modulo p multiplications of (m2-bit value)*2k+m1, wherein the addition means adds up residues respectively read out from the first part table means and the second part table means and the lower data.
-
-
17. The modular multiplication apparatus of claim 14, wherein
the m bits are divided into t bit-sequences respectively having m1 bits, m2 bits, . . . mt bits in order from lower bits, wherein 3≦ - t≦
m,each m-bit value corresponds to a combination of values respectively represented by t bit-sequences mi, wherein i represents integers in a range of 1 to t, the table means includes;
t partial table means Ti which each prestore residues of modulo p multiplications of (a value represented by bit-sequences mi)*2k+x, wherein x=m1+m2+ . . . +m(i−
1), andthe addition means adds up t residues respectively read out by the read means from the t partial table means Ti and the lower data.
- t≦
-
18. The modular multiplication apparatus of claim 14, wherein
the m bits are divided into t bit-sequences respectively having m1 bits, m2 bits, . . . mt bits in order from lower bits, wherein 2≦ - t≦
m,the table means includes;
t partial table means Ti which each prestore residues of modulo p multiplications of (a value represented by bit-sequences mi)*2k+x, wherein the addition means adds up t residues respectively read out by the read means from the t partial table means Ti and the lower data, wherein a result of this addition is equivalent to the other intermediate value.
- t≦
-
19. The modular multiplication apparatus of claim 18, wherein
each of the t partial table means Ti prestores each of the residues as k-bit data. -
20. The modular multiplication apparatus of claim 19 further comprising:
- an accumulation means; and
a correction means, whereinthe accumulation means includes;
a third register for holding 0 as an initial value; and
an adder for adding up the partial products C(i)*b[s*i+s−
1;
s*i] and the accumulated value stored in the third register and storing a result of this addition into the third register as another accumulated value, whereinthe correction means includes;
a correction value hold means for holding a correction value being an integral multiple of P; and
a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
- an accumulation means; and
-
21. The modular, multiplication apparatus of claim 20, wherein
the third register includes a sign bit, the correction control means allows the adder to subtract the correction value from the accumulated value at the same time when the adder adds up the partial product and the accumulated value stored in the third register when the accumulated value is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1)(2s− - 1) P of the partial product.
-
22. The modular multiplication apparatus of claim 18, wherein
the modulo P multiplication satisfies P=2k− - α
,each of the t partial table means Ti prestores each of the residues as k3-bit data, wherein k3 is equivalent to the number of bits in t*2m*α
, and α
is a constant defined to satisfy a condition that k3 is smaller than k.
- α
-
23. The modular multiplication apparatus of claim 22, wherein
each of the t partial table means Ti includes 2mi entries which respectively correspond to values in a range of 0 to (2mi− - 1) each having mi bits, wherein
the jth entry stores (j−
1)*2m1+ . . . +m(i−
1)*α
, wherein j=1, . . . 2mi.
- 1) each having mi bits, wherein
-
24. The modular multiplication apparatus of claim 23 further comprising an accumulation means;
- and a correction means, wherein
the accumulation means includes;
a third register for holding 0 as an initial value; and
an adder, for adding up the partial products C(i)*b[s*i+s−
1;
s*i] and the accumulated value stored in the third register and storing a result of this addition into the third register as another accumulated value, whereinthe correction means includes;
a correction value hold means for holding a correction value being an integral multiple of P; and
a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
- and a correction means, wherein
-
25. The modular multiplication apparatus of claim 24, wherein
the third register includes a sign bit, the correction control means allows the adder to subtract the correction value from the accumulated value at the same time when the adder adds up the partial product and the accumulated value stored in the third register when the accumulated value is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1)(2s− - 1) P of the partial product.
-
26. A modular multiplication apparatus for calculating a congruent value of a modulo p multiplication of a product of a multiplicand and a multiplier, wherein P is k-bit data, the modular multiplication apparatus comprising;
-
an output means for outputting, in order from lower bits, partial multipliers which are s-bit parts making up the multiplier, wherein s is an integer 2 or larger;
a first calculation means for obtaining shifted multiplicands by shifting the multiplicand in accordance with a place of each partial multiplier, and for calculating congruent values of a modulo p multiplication of respective shifted multiplicands, wherein the congruent values obtained here are referred to as intermediate values;
a second calculation means for calculating partial products by multiplying the partial multipliers output from the output means by the corresponding intermediate values output from the first calculation means;
an accumulation means for accumulating the partial products output from the second calculation means and outputting an accumulated value;
a correction means for performing a correction so that the accumulated value does not exceed a predetermined number of bits by adding/subtracting an integral multiple of p to/from the accumulated value; and
a control means for allowing the first calculation means, the second calculation means the accumulation means, and the collection means to repeatedly perform the respective operations for each of the partial multipliers output from the output means, wherein the first calculation means includes;
a table means which prestores residues of modulo p multiplications of (m-bit value)*2k, wherein m is an integer s or larger, wherein the first calculation means outputs the multiplicand as an intermediate value first time, and second time and after, obtains a shifted intermediate value by performing a shift of s bits on a preceding intermediate value, refers to the table means to read out a residue corresponding to m bits adjacent to lower k bits of the shifted intermediate value, and calculates another intermediate value by adding up the read-out residue and the lower k bits. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
the first calculation means includes: a first hold means for holding an intermediate value;
a shift means for obtaining the shifted intermediate value by performing a shift of s bits on the intermediate value held by the first hold means in correspondence to each partial multiplier output from the output means second time and after;
a division means for dividing the shifted intermediate value into a higher data and a lower data, wherein the higher data is composed of m bits adjacent to lower k bits of the shifted intermediate value, and the lower data is composed of the lower k bits;
a read means for referring to the table means to read out a residue corresponding to the higher data; and
an addition means for calculating another intermediate value by adding up the read-out residue and the lower data, wherein the first hold means updates the intermediate value to the other intermediate value calculated by the addition means, and outputs the multiplicand as an intermediate value first time, and outputs the updated intermediate value second time and after, and the second calculation means calculates partial products by using the intermediate value held by the first hold means.
-
-
28. The modular multiplication apparatus of claim 27, wherein
the table means includes: a memory device which prestores residues of modulo p multiplications of (m-bit value)*2k, wherein storage areas of residues respectively correspond to addresses to be input, and the addresses further correspond to m-bit values.
-
29. The modular multiplication apparatus of claim 27, wherein
the m bits are divided into lower m1 bits and higher m2 bits, wherein m=m1+m2, each m-bit value corresponds to a combination of an m1-bit value and an m2-bit value, the table means includes: -
a first part table means which prestores residues of modulo p multiplications of (m1-bit value)*2k; and
a second part table means which prestores residues of modulo p multiplications of (m2-bit value)*2k+m1, wherein the addition means adds up residues respectively read out from the first part table means and the second part table means and the lower data.
-
-
30. The modular multiplication apparatus of claim 27, wherein
the m bits are divided into t bit-sequences respectively having m1 bits, m2 bits, mt bits in order from lower bits, wherein 3≦ - t≦
m,each m-bit value corresponds to a combination of values respectively represented by t bit-sequences mi, wherein i represents integers in a range of 1 to t, the table means includes;
t partial table means Ti which each prestore residues of modulo p multiplications of (a value represented by bit-sequences mi)*2k+x, wherein x=m1+m2+ . . . +m(i−
1), andthe addition means adds up t residues respectively read out by the read mean from the t partial table means Ti and the lower data.
- t≦
-
31. The modular multiplication, apparatus of claim 27, wherein
the control means controls a pipeline process which includes a first stage, a second stage, and a third stage, and in the first stage, the control means allows the output means to output a partial multiplier and allows the first calculation means to output an intermediate value, in the second stage, the control means allows the second calculation means to output a partial product, and in the third stage, the control means allows the accumulation means to accumulate partial products and allows the correction on means to perform correction. -
32. The modular multiplication apparatus of claim 31, wherein
the output means includes: -
a multiplier hold means for holding the multiplier as an initial value and outputting a partial multiplier which is composed of lower s bits of a value currently held in the multiplier hold means;
a shift right means for performing a shift right of s bits on a value held by the multiplier hold means and outputting the right-shifted value to the multiplier hold means so that the right-shifted value is stored in the multiplier hold means.
-
-
33. The modular multiplication apparatus of claim 32, wherein
the second calculation means includes: -
a multiplication means for calculating the partial product of the intermediate value held by the first hold means and the partial multiplier output from the multiplier hold means; and
a second hold means for holding the partial product calculated by the multiplication means.
-
-
34. The modular multiplication apparatus of claim 33, wherein
the accumulation means includes: -
a third hold means for holding the accumulated value; and
an adder for adding up the partial product held by the second hold means and the accumulated value held by the third hold means and outputting a result value, wherein the third hold means holds the result value output from the adder as the accumulated value.
-
-
35. The modular multiplication apparatus of claim 34, wherein
the correction means includes: -
a correction value hold means for holding a correction value being the integral multiple of P; and
a correction control means for when the number of effective bits of the accumulated value stored in the third hold means exceeds a predetermined value, allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value at the same time the adder adds up the partial product and the accumulated value.
-
-
36. The modular multiplication apparatus of claim 35, wherein
the control means controls the pipeline process using the first hold means and the multiplier hold means as pipeline latches between the first stage and the second stage, and using the second hold means as a pipeline latch between the second stage and the third stage. -
37. The modular multiplication apparatus of claim 31, wherein
the table means includes: a memory device which prestores residues of modulo p multiplications of (m-bit value)*2k, wherein storage areas of residues respectively correspond to addresses to be input, and the addresses further correspond to m-bit values.
-
38. The modular multiplication apparatus of claim 31, wherein
the m bits are divided into lower m1 bits and higher m2 bits, wherein m=m1+m2, each m-bit value corresponds to a combination of an m1-bit value and an m2-bit value, the table means includes: -
a first part table means which prestores residues of modulo p multiplications of (m1-bit value)*2k; and
a second part table means which prestores residues of modulo p multiplications of (m2-bit value)*2k+m1, wherein the addition means adds up residues respectively read out from the first part table means and the second part table means and the lower data.
-
-
39. The modular multiplication apparatus of claim 31, wherein
the m bits are divided into t bit-sequences respectively having m1 bits, m2 bits, . . . mt bits in order from lower bits, wherein 3≦ - t≦
m,each m-bit value corresponds to a combination of values respectively represented by t bit-sequences mi, wherein i represents integers in a range of 1 to t, the table means includes;
t partial table means Ti which each prestore residues of modulo p multiplications of (a value represented by bit-sequences mi)*2k+x, wherein x=m1+m2+ . . . +m(i−
1), andthe addition means adds up t residues respectively read out by the read means from the t partial table means Ti and the lower data.
- t≦
-
40. The modular multiplication apparatus of claim 27, wherein
the second calculation mean includes: -
a judgment means for judging whether all bits of the s-bit partial multiplier output from the output means are 1;
a first generation means for generating a product of a multiplication of the intermediate value and 2s; and
generating a negative value of the multiplicand;
a second generation means for generating a product of a multiplication of the, intermediate value and a bit weight of each bit of the partial multiplier, wherein the product is equivalent to the intermediate value shifted by the number of bits corresponding to each bit weight; and
a second addition means for;
adding up each value generated by, the first generation means when the judgment means judges that the all bits are 1; and
adding up products corresponding to bits being binary value “
1”
in the partial multiplier out of the products generated by the second generation means when the judgment means does not judge that the all bits are 1.
-
-
41. The modular multiplication apparatus of claim 40, wherein
the second generation means includes: -
ith shift means for obtaining a shifted intermediate value by, performing a shift of i bits on the intermediate value calculated by the first calculation means, wherein i represents integers in a range of 1 to (s−
1),the first generation means includes;
sth shift means for obtaining a shifted intermediate value by performing a shift of s bits on the intermediate value calculated by the first calculation means;
a complement generation means for generating a one'"'"'s complement of the intermediate value; and
a constant output means for outputting a constant 1, wherein the second addition means includes;
a selection means for;
selecting the shifted intermediate value output from the sth shift means, the one'"'"'s complement generated by the complement generation means, and the constant 1 when the judgment means'"'"' judges that the all bits are 1; and
selecting the intermediate value when a bit at a place of 20 of the partial multiplier has binary value “
1”
when the judgment means does not judge that the all bits are 1; and
selecting the shifted intermediate value output from the ith shift means when a bit at a place of 2i of the partial multiplier has binary value “
1”
when the judgment means does not judge that the all bits are 1; and
an adder for calculating the partial product by adding up values selected by the selection means.
-
-
42. The modular multiplication apparatus of claim 27, wherein
s=3n, the partial multiplier is divided into n 3-bit data sequences s1, . . . sn in order from lower bits, the second calculation means includes: -
jth judgment means for judging whether the 3-bit data sequence sj is (111)2, wherein j represents integers in a range of 1 to n, jth special generation means for generating a product of I*(1000)2*23(j−
1) (I representing the intermediate value) and generating N (N representing a negative value of I*23(j−
1) when the jth judgment means judges that the 3-bit data sequence sj is (111)2, wherein 23(j−
1) corresponds to a place of the 3-bit data sequence sj;
jth general generation means for generating, for each bit of the 3-bit data sequence sj, products of multiplications of a logical value of a current bit, each bit weight of each bit in the s-bit partial multiplier, and the intermediate value when the jth judgment means does not judge that the 3-bit data sequence sj is (111)2, wherein the product is equivalent to the intermediate value shifted by the number of bits corresponding to the bit weight; and
a second addition means for adding up the products generated by the jth special generation means and the jth general generation means.
-
-
43. The modular multiplication apparatus of claim 42, wherein
the second calculation means includes: -
ith shift means for obtaining a shifted intermediate valve by performing a shift of i bits on the intermediate value, wherein i represents integers in a range of 1 to s, wherein the jth general generation means when j=1 uses shifted intermediate values obtained by the ith shift means when i=1, 2, the jth general generation means when j≠
1 uses shifted intermediate values obtained by the (3j−
3)th shift means, the (3j−
2)th shift means, and the (3j−
1) shift means,the jth special generation means uses shifted intermediate values obtained by the 3jth shift means, and the jth special generation means and the (j+1) general generation means share the 3jth shift means.
-
-
44. The modular multiplication apparatus of claim 43, wherein
the jth special generation means includes: -
a complement generation means for generating one'"'"'s complement of either of the intermediate value and the shifted intermediate value obtained by the (3j−
3)th shift means; and
a constant output means for outputting the constant 1, the second addition means includes;
a selection means for;
selecting the shifted intermediate value output from the 3jth shift means, the one'"'"'s complement generated by the complement generation means of the jth special generation means, and the constant 1 output from the constant output means of the jth special generation means when the jth judgment means judges that the 3-bit data sequence sj is (111)2;
selecting the intermediate value and outputs from the (3j−
2)th shift means and the (3j−
1)th shift means when the jth judgment means does not judge that the 3-bit data sequence s1, is (111)2; and
selecting outputs from the (3j−
3)th shift means, the (3j−
2)th shift means, and the (3j−
1)th shift means when the jth judgment means does not judge that the 3-bit data sequence sj except for the 3-bit data sequence s1 is (111)2; and
an adder for calculating the partial product by adding up values selected by the selection means.
-
-
45. The modular multiplication apparatus of claim 27 further comprising:
a post-processing means for using the division means, the read means, and the addition means to obtain a residue of a modulo p multiplication of a last accumulated value having been corrected by the correction means, wherein the last accumulated value is an accumulated value corrected by the correction means in correspondence to the partial multiplier output last from the output means.
-
46. A modular multiplication apparatus for calculating a k1-bit congruent value of a modulo p multiplication of a product of a k-bit multiplicand a and a k-bit multiplier b, wherein P is k-bit and k1≦
- k, the modular multiplication apparatus comprising;
an output means for outputting, in order from lower bits, partial multipliers which are s-bit parts making up the multiplier, wherein s is an integer 2 or larger;
a first calculation means, including a k2-bit first register which stores the multiplicand a as initial data, wherein k2≧
k, for calculating a congruent value of a modulo p multiplication of a value being data in the first register shifted and storing the obtained congruent value in the first register, wherein the congruent value obtained here is referred to as intermediate value;
a second calculation means, including a second register which stores 0 as initial data, for calculating partial products by multiplying the partial multipliers output from the output means by the data stored in the first register and storing the calculated partial products in the second register;
an accumulation means, including a third register which stores 0 as initial data, for accumulating the partial products output from the second calculation means and adding an accumulated value to data in the third register;
a correction means for correcting the accumulated value by adding/subtracting an integral multiple of p to/from the accumulated value so that a congruent Value of a modulo P multiplication whose absolute value is smaller than an absolute value of the accumulated value is obtained; and
a control means for allowing the first calculator means, the second calculation means, the accumulation means, and the correction means to repeatedly perform the respective operations for each of the partial multipliers output from the output means, wherein the first calculation means includes;
a table means which prestores residues of modulo p multiplications of m-bit value, wherein m=s+k2−
k, whereinthe first calculation means outputs the multiplicand as an intermediate value first time, and second time and after, obtains a shifted intermediate value by performing a shift of s bits on a preceding intermediate value, refers to the table means to read out a residue corresponding to m bits adjacent to lower k bits of the shifted intermediate value, and calculates another intermediate value by adding up the read-out residue and the lower k bits. - View Dependent Claims (47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74)
the first calculation means includes: a shift means for obtaining the shifted intermediate value by performing a shift of s bits on a preceding k2-bit intermediate value output from the first register in correspondence to each partial multiplier output from the output means second time and after;
a division means for dividing the shifted intermediate value into a higher data and a lower data, wherein the higher data is composed of m bits adjacent to lower k bits of the shifted intermediate value, and the lower data is composed of the lower k bits;
a read means for referring to the table means to read out a residue corresponding to the higher data; and
an addition means for calculating another intermediate value by adding up the read-out residue and the lower data, wherein the first register updates the intermediate value to the other intermediate value calculated by the addition means.
- k, the modular multiplication apparatus comprising;
-
48. The modular multiplication apparatus of claim 47 wherein
the m bits are divided into t bit-sequences respectively having m1 bits, m2 bits, . . . mt bits in order from lower bits, wherein 2≦ - t≦
m,the table means includes;
t partial table means Ti which each prestore residues of modulo p multiplications of (a value represented by bit-sequences mi)*2k+x, wherein the addition means adds up t residues respectively read out by the read means from the t partial table means Ti and the lower data, wherein a result of this addition is equivalent to the other intermediate value.
- t≦
-
49. The modular multiplication apparatus of claim 48, wherein
each of the t partial table means Ti prestores each of the residues as k-bit data. -
50. The modular, multiplication apparatus of claim 49, wherein
the accumulation means includes: -
an adder for adding up the partial products calculated by the second calculation means and the accumulated value stared in the third register and storing a result of this addition into the third register as another accumulated value, wherein the correction means includes;
a correction value hold means for holding a correction value being an integral multiple of P; and
a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
-
-
51. The modular multiplication apparatus of claim 50, wherein
the third register includes a sign bit, the correction control means allows the adder to subtract the correction value at the same time the adder adds up the partial product and the accumulated value when the accumulated value stored in the third register is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1)(2s− - 1) P of the partial product.
-
52. The modular multiplication apparatus of claim 48, wherein
the modulo P multiplication satisfies P=2k− - α
,each of the t partial table means Ti prestores each of the residues as k3-bit data, wherein k3 is equivalent to the number of bits in t*2m*α
, and α
is a constant defined to satisfy a condition that k3 is smaller than k.
- α
-
53. The modular multiplication apparatus of claim 52, wherein
each of the partial table means Ti includes 2mi entries which respectively correspond to values in a range of 0 to (2mi− - 1) each having mi bits, wherein
the jth entry stores (j−
1)*2m1+ . . . +m(i−
1)*α
, wherein j=1, . . . 2mi.
- 1) each having mi bits, wherein
-
54. The modular multiplication apparatus of claim 53, wherein
the accumulation means includes: -
an adder for adding up the partial products calculated by the second calculation means and the accumulated value stored in the third register and storing a result of this addition into the third register as another accumulated value, wherein the correction means includes;
a correction value - hold means for holding a correction value being an integral multiple of P; and
a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
-
-
55. The modular multiplication apparatus of claim 54, wherein
the third register includes a sigh bit, the correction, control means allows the adder to subtract the correction value at the same time the adder adds up the partial product and the accumulated value when the accumulated value stored in the third register is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1)(2G− - 1) P of the partial product.
-
56. The modular multiplication apparatus, of claim 48, wherein
the control means controls a pipeline process which includes a first stage, a second stage, and a third stage, and in the first stage, the control means allows the output means to output a partial multiplier and allows the first calculation means to output an intermediate value, in the second stage, the control means allows the second calculation means to output a partial product, and in the third stage, the control means allows the accumulation means to accumulate partial products and allows the correction means to perform correction. -
57. The modular multiplication apparatus of claim 56, wherein
the output means includes: -
a multiplier hold means for holding the multiplier as an initial value and outputting a partial multiplier which is composed of lower s bits of a value currently held in the multiplier hold means;
a shift right means for performing a shift right of s bits on a value hold by the multiplier hold means and outputting the right-shifted value to the multiplier hold means so that the right-shifted value is stored in the multiplier hold means.
-
-
58. The modular multiplication apparatus of claim 57, wherein
the second calculation means includes: -
a multiplication means for calculating the partial product of the intermediate value held by the first hold means and the partial multiplier output from the multiplier hold means; and
a second hold means for holding the partial product calculated by the multiplication means.
-
-
59. The modular multiplication apparatus of claim 58, wherein
the accumulation means includes: -
a third hold means for holding the accumulated value; and
an adder for adding up the partial product held by the second hold means and the accumulated value held by the third hold means and outputting a result value, wherein the third hold means holds the result value output from the adder as the accumulated value.
-
-
60. The modular multiplication apparatus of claim 59, wherein
the correction means includes: -
a correction value hold means for holding a correction value being the integral multiple of P; and
a correction control means for, when the number of effective bits of the accumulated value stored in the third hold means exceeds a predetermined value, allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value at the same time the adder adds up the partial product and the accumulated value.
-
-
61. The modular multiplication apparatus of claim 60, wherein
the control means controls the pipeline process using the first hold means and the multiplier hold means as pipeline latches between the first stage and the second stage, and using the second hold means as a pipeline latch between the second stage and the third stage. -
62. The modular multiplication apparatus of claim 56, wherein
each of the t partial table means Ti prestores each of the residues as k-bit data. -
63. The modular multiplication apparatus of claim 62, wherein
the accumulation means includes: -
an adder for adding up the partial products calculated by the second calculation means and the accumulated value stored in the third register and, storing a result of this addition into the third register as another accumulated value, wherein the correction means includes;
a correction value hold means for holding a correction value being an integral multiple of P; and
a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
-
-
64. The modular multiplication apparatus of claim 63, wherein
the third register includes a sign bit, the correction control means allows the adder to subtract the correction value at the same time the adder adds up the partial product and the accumulated value when the accumulated value stored in the third register is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1)(2s− - 1) P of the partial product.
-
65. The modular multiplication apparatus of claim 56, wherein
the modulo P multiplication satisfies P=2k− - α
,each of the t partial table means Ti prestores each of the residues as k3-bit data, wherein k3 is equivalent to the number of bits in t*2m*α
, and α
is a constant defined to satisfy a condition that k3 is smaller than k.
- α
-
66. The modular multiplication apparatus of claim 65, wherein
each of the t partial table means Ti includes 2mi entries which respectively correspond to values in a range of 0 to (2mi− - 1) each having mi bits, wherein
the jth entry stores (j−
1)*2m1+ . . . +m(i−
1)*α
, wherein j=1, . . . 2mi.
- 1) each having mi bits, wherein
-
67. The modular multiplication apparatus of claim 66, wherein
the accumulation means includes: -
an adder for adding up the partial products calculated by the second calculation means and the accumulated value stored in the third register and storing a result of this addition into the third register as another accumulated value, wherein the correction means includes;
a correction value, hold means for holding a correction value being an integral multiple of P; and
a correction control means for allowing the adder to subtract the correction value held by the correction value hold means from the accumulated value held by the third register when the accumulated value is larger than a predetermined value.
-
-
68. The modular multiplication apparatus of claim 67, wherein
the third register includes a sign bit, the correction control means allows the adder to subtract the correction value at the same time the adder adds up the partial product and the accumulated value when the accumulated valve stored in the third register is positive, and the correction value is an integral multiple of P and the absolute value of the correction value is equivalent to or smaller than a maximum value (t+1)(2s− - 1) P of the partial product.
-
69. The modular multiplication apparatus of claim 48, wherein
the second calculation means Includes: -
a judgment means for judging whether all bits of the s-bit partial multiplier output from the output means are 1;
a first generation means for generating a product of a multiplication of the intermediate value and 2s; and
generating a negative value of the multiplicand;
a second generation means for generating a product of a multiplication of the intermediate value and a bit weight of each bit of the partial multiplier, wherein the product is equivalent to the intermediate value shifted by the number of bits corresponding to each bit weight; and
a second addition means for;
adding up each value generated by the first generation means when the judgment means judges that the all bits are 1; and
adding up products corresponding to bits being binary value “
1”
in the partial multiplier out of the products generated by the second generation means when the judgment means does not judge that the all bits are 1.
-
-
70. The modular multiplication apparatus of claim 69, wherein
the second generation means includes: -
ith shift means for obtaining a shifted intermediate value by performing a shift of i bits on the intermediate value calculated by the first calculation means, wherein i represents integers in a range of 1 to (s−
1),the first generation means includes;
sth shift mean for obtaining a shifted intermediate value by performing a shift of s bits on the intermediate value calculated by the first calculation means;
a complement generation means for generating a one'"'"'s complement of the intermediate value; and
a constant output meant for outputting a constant 1, wherein the second addition means includes;
a selection means for;
selecting the shifted intermediate value output from the sth shift means, the one'"'"'s complement generated by the complement generation means, and the constant 1 when the judgment means judges that the all bits are 1; and
selecting the intermediate value when a bit at a place of 20 of the partial multiplier has binary value “
1”
when the judgment means does not judge that the all bits are 1; and
selecting the shifted intermediate value output from the 1th shift means when a bit at a place of 2i of the partial multiplier has binary value “
1”
when the judgment means does not judge that the all bits are 1; and
an adder for calculating the partial product by adding up values selected by the selection means.
-
-
71. The modular multiplication apparatus of claim 48, wherein
s=3n, the partial multiplier is divided into n 3-bit data sequences s1, . . . sn in order from lower bits, the second calculation means includes: -
jth judgment means for judging whether the 3-bit data sequence sj is (111)2, wherein j represents integers in a range of 1 to n, jth special generation means for generating a product of I*(1000)2*23(j−
1) (I representing the intermediate value) and generating N (N representing a negative value of I*23(j−
1)) when the jth judgment means judges that the 3-bit data sequence sj is (111)2, wherein 23(j−
1) corresponds to a place of the 3-bit data sequence sj;
jth general generation means for generating, for each bit of the 3-bit data sequence sj, products of multiplications of a logical value of document bit, each bit weight of each bit in the s-bit partial multiplier, and the intermediate value when the jth judgment means does not judge that the 3-bit data sequence sj is (111)2, wherein the product is equivalent to the intermediate value shifted by the number of bits corresponding to the bit weight; and
a second addition means for adding up the products generated by the jth special generation means and the jth general generation means.
-
-
72. The modular multiplication apparatus of claim 71, wherein
the second calculation means includes: -
ith shift means for obtaining a shifted intermediate value by performing a shift of i bits on the intermediate value, wherein i represents integers in a range of 1 to s, wherein the jth general generation means when j=1 uses shifted intermediate values obtained by the ith shift means when i=1, 2, the jth general generation means when j≠
1 uses shifted intermediate values obtained by the (3j−
3)th shift means, the (3j−
2)th shift means, and the (3j−
1)th shift means,the jth special generation means uses shifted intermediate values obtained by the 3jth shift means, and the jth special generation means and the (j+1) general generation means share the 3jth shift means.
-
-
73. The modular multiplication apparatus of claim 72, wherein
the jth special generation means includes: -
a complement generation means for generating one'"'"'s complement of either of the intermediate value and the shifted intermediate value obtained by the (3j−
3)th shift means; and
a constant output means for outputting the constant 1, the second addition means includes;
a selection means for;
selecting the shifted intermediate value output from the 3jth shift means, the one'"'"'s complement generated by the complement generation means of the jth special generation means, and the constant 1 output from the constant output means of the jth special generation means when the jth judgment means judges that the 3-bit data sequence sj is (111)2;
selecting the intermediate value and outputs from the (3j−
2)th shift means and the (3j−
1)th shift means when the jth judgment means does not judge that the 3-bit data sequence s1 is (111)2; and
selecting outputs from the (3j−
3)th shift means, the (3j−
2)th shift means, and the (3j−
1)th shift means when the jth judgment means does not judge that the 3-bit data sequence sj except for the 3-bit date, sequence s1 is (111)2; and
an adder for calculating the partial product by adding up values selected by the selection means.
-
-
74. The modular multiplication apparatus of claim 48 further comprising:
a post-processing means for using the division means, the read means, and the addition means to obtain a residue of a modulo P multiplication of a last accumulated value having been corrected by the correction means, wherein the last accumulated value is an accumulated value corrected by the correction means in correspondence to the partial multiplier output last from the output means.
-
75. A modular multiplication apparatus for calculating a congruent value of a modulo P multiplication of a product of a multiplicand and a multiplier, wherein P is k-bit data, the modular multiplication apparatus comprising:
-
an output means for outputting, in order from lower bits, partial multipliers which are s-bit parts making up the multiplier, wherein s is an integer 2 or larger;
a first calculation means for obtaining shifted multiplicands by shifting the multiplicand in accordance with a place of each partial multiplier, and, for calculating congruent values of a modulo p multiplication of respective shifted multiplicands, wherein the congruent values obtained here are referred to as intermediate values;
a second calculation Means for calculating partial products by multiplying the partial multipliers output from the output means by the corresponding intermediate values output from the first calculation means;
an accumulation means for accumulating the partial products output from the second calculation means and outputting an accumulated value;
a correction means for performing a correction so that the accumulated value does not exceed a predetermined number of bits by adding/subtracting an integral multiple of p to/from the accumulated value; and
a control means for allowing the first calculation means, the second calculation means, the accumulation means, and the correction means to repeatedly perform the respective operations for each of the partial multipliers output from the output means, wherein the second calculation means includes;
a judgment means for judging whether all bits of the s-bit partial multiplier output from the output means are 1;
a first generation means for generating a product of the intermediate value*2s; and
generating a negative value of the multiplicand;
a second generation means for generating a product of the intermediate value and a bit weight of each bit of the partial multiplier, wherein the product is equivalent to the intermediate value shifted by the number of bits corresponding to each bit weight;
an addition means for;
adding up each value generated by the first generation means when the judgment means judges that the all bits are 1; and
adding up products corresponding to bits being binary value “
1”
in the partial multiplier out of the products generated by the second generation means when the judgment means does not judge that the all bits are 1.- View Dependent Claims (76)
the second calculation means includes: a judgment means for judging whether all bits of the s-bit partial multiplier output from the output means are 1;
a first generation means for generating a product of a multiplication of the intermediate value and 2s; and
generating a negative value of the multiplicand;
a second generation means for generating a product of a multiplication of the intermediate value and a bit weight of each bit of the partial multiplier, wherein the product is equivalent to the intermediate value shifted by the number of bits corresponding to each bit weight; and
a second addition means for;
adding up each value generated by the first generation means when the judgment means judges that the all bits are 1; and
adding up products corresponding to bits being binary value “
1”
in the partial multiplier out of the products generated by the second generation means when the judgment means does not judge that the all bits are 1.
-
-
77. A modular multiplication apparatus for calculating a congruent value of a modulo p multiplication of a product of a multiplicand and a multiplier, wherein P is k-bit data, the modular multiplication apparatus comprising:
-
an output means for outputting, in order from lower bits, partial multipliers which are s-bit parts making up the multiplier, wherein s is an integer 2 or larger;
a first calculation means for obtaining shifted multiplicands by shifting the multiplicand in accordance with a place of each partial multiplier, and for calculating congruent values of a modulo p multiplication of respective shifted multiplicands, wherein the congruent values obtained here are referred to as intermediate values;
a second calculation means for calculating partial products by multiplying the partial multipliers output from the output means by the corresponding intermediate values output from the first calculation means;
an accumulation means for accumulating the partial products output from the second calculation means and outputting an accumulated value;
a correction means for performing a correction so that the accumulated value does not exceed a predetermined number of bits by adding/subtracting an integral multiple of p to/from the accumulated value; and
a control means for allowing the first calculation means, the second calculation means, the accumulation means, and the correction means to repeatedly perform the respective operations for each of the partial multipliers output from the output means, wherein s=3n, the partial multiplier is divided into n 3-bit data sequences sn, . . . s1 in order from lower bits, the second calculation means includes;
jth judgment means for judging whether the 3-bit data sequence s1, is (111)2, wherein j represents integers in a range of 1 to n, jth special generation means for generating a product of the intermediate value*(1000)2*23(j−
1) and generating (a negative value of the multiplicand)*23(j−
1) when the jth judgment means judges that the 3-bit data sequence sj is (111)2, wherein 23(j−
1) corresponds to a place of the 3-bit data sequence sj;
jth general generation means for generating, for each bit of the 3-bit data sequence sj, a product of (a logical value of a current bit)*(a bit weight of the current bit in the s-bit partial multiplier)*the intermediate value when the jth judgment means does not judge that the 3-bit data sequence sj is (111)2, wherein the product is equivalent to the intermediate value shifted by the number of bits corresponding to each bit weight; and
an addition means for adding up the products generated by the jth special generation means and the jth general generation means. - View Dependent Claims (78, 79)
the second calculation means includes: ith shift means for obtaining a shifted intermediate value by performing a shift of i bits on the intermediate value, wherein i represents integers in a range of 1 to s, wherein the jth general generation means when j=1 uses shifted intermediate values obtained by the jth shift means when i=1, 2, the jth general generation means when j≠
1 uses shifted intermediate values obtained by the (3j−
3)th shift means, the (3j−
2)th shift means, and the (3j−
1) shift means,the jth special generation means uses shifted intermediate values obtained by the 3jth shift means, and the jth special generation means and the (j+1) general generation means share the 3jth shift means.
-
-
79. The modular multiplication apparatus of claim 78, wherein
the jth special generation means includes: -
a complement generation means for generating one'"'"'s complement of either of the intermediate value and the shifted intermediate value obtained by the (3j−
3)th shift means; and
a constant output means for outputting the constant 1, the second addition means includes;
a selection means for;
selecting the shifted intermediate value output from the 3jth shift means, the one'"'"'s complement generated by the complement generation means of the jth special generation means, and the constant 1 output from the constant output means of the jth special generation means when the jth judgment means judges that the 3-bit data sequence sj is (111)2;
selecting the intermediate value and outputs from the (3j−
2)th shift means and the (3j−
1)th shift means when the jth judgment means does not judge that the 3-bit data sequence s1 is (111)2; and
selecting outputs from the (3j−
3)th shift means, the (3j−
2) shift means, and the (3j−
1)th shift means when the jth judgment means does not judge that the 3-bit data sequence sj except for the 3-bit data sequence s1 is (111)2; and
an adder for calculating the partial product by adding up values selected by the selection means.
-
Specification