Modular-multiplication computing unit and information-processing unit
Either a multiplicand A or 0 is selected, depending on the value of multiplier B supplied in a unit composed of q bits through the use of selectors, and the selected result is provided, and either a multiplicand u or 0 is selected, depending on the value of multiplier N supplied in a unit composed of q bits through the use of selectors, and the selected result is provided. A carry save adder implements the operation of A×B+u×N making use of the values successively supplied from the selectors. To the operation result of A×B+u×N supplied from the carry save adder in a unit composed of q bits is added the operation result of A×B+u×N in the past supplied in a unit composed of q bits and the added result is issued as a result of the modular-multiplication operation S.
1 . A modular-multiplication computing unit for computing S=S+A×B+u×N wherein A and u denote multiplicands, B and N denote multipliers and S denotes a result of modular-multiplication operation, comprising:
selectors that select either a value of said multiplicand A or a value of 0, depending on a value of said multiplier B supplied in a unit composed of a plurality of bits q, and supply the selected result and that select either a value of said multiplicand u or the value of 0, depending on a value of said multiplier N supplied in a unit composed of said plurality of bits q, and supply the selected result,
a carry save adder that executes the operation of A×B+u×N through the use of values successively supplied from said selectors, and
an adder that adds the operation result of said A×B+u×N supplied in a unit composed of said q bits from said carry save adder and the operation result made in the past supplied in a unit composed of said q bits and provides the added result as said result of modular-multiplication operation S.
2 . The modular-multiplication computing unit according to claim 1 , further comprising a first memory element that keeps said multiplicand A and supplies it to said selector,
a second memory element that keeps said multiplicand u and supplies it to said selector,
a third memory element that keeps said multiplier B and supplies it to said selector in a unit composed of said q bits,
a fourth memory element that keeps said multiplier N and supplies it to said selector in a unit composed of said q bits, and
a fifth memory element that keeps said result of modular-multiplication operation S supplied from said adder and supplies said result of modular-multiplication operation S to said adder in a unit composed of said q bits.
3 . The modular-multiplication computing unit according to claim 1 , further comprising a control unit that controls the operation of said carry save adder.
4 . The modular-multiplication computing unit according to claim 3 , wherein said control unit
sets said multiplicand A to said first memory element,
sets said multiplicand u to said second memory element,
sets said multiplier B to said third memory element,
sets said multiplier N to said fourth memory element, and
supplies 0 to said selector.
5 . The modular-multiplication computing unit according to claim 3 , further comprising a u-generating unit that stores pre-computed relationships of the values of said multiplicand u to the values of said multiplicand A, said multiplier B, said multiplier N and said result of modular-multiplication operation S, wherein
said control unit, when computing said S=S+A×B+u×N, consults said u-generating unit and determines the value of said multiplicand u.
6 . The modular-multiplication computing unit according to claim 1 , wherein said bit number q is 2.
7 . The modular-multiplication computing unit according to claim 1 , wherein said bit number q is 4.
8 . The modular-multiplication computing unit according to claim 2 , wherein said first memory element and said second memory element are latch circuits.
9 . The modular-multiplication computing unit according to claim 2 , wherein said third memory element, said fourth memory element and said fifth memory element are shift registers.
10 . An information processing unit, comprising:
a modular-multiplication computing unit according to claim 1 ,
a first memory element that keeps said multiplicand A and supplies it to said selector,
a second memory element that keeps said multiplicand u and supplies it to said selector,
a third memory element that keeps said multiplier B and supplies it to said selector in a unit composed of said q bits,
a fourth memory element that keeps said multiplier N and supplies it to said selector in a unit composed of said q bits, and
a fifth memory element that keeps said result of modular-multiplication operation S supplied from said adder and supplies said result of modular-multiplication operation S to said adder in a unit composed of said q bits.
11 . The information processing unit according to claim 10 , further comprising a control unit that controls the operation of said carry save adder.
12 . The information processing unit according to claim 11 , wherein said control unit
sets said multiplicand A to said first memory element,
sets said multiplicand u to said second memory element,
sets said multiplier B to said third memory element,
sets said multiplier N to said fourth memory element, and
supplies 0 to said selector.
13 . The information processing unit according to claim 11 , further comprising a u-generating unit that stores pre-computed relationships of the values of said multiplicand u to the values of said multiplicand A, said multiplier B, said multiplier N and said result of modular-multiplication operation S, wherein
said control unit, when operating said S=S+A×B+u×N, consults said u-generating unit and determines the value of said multiplier u.
14 . The information processing unit according to claim 10 , wherein said bit number q is 2.
15 . The information processing unit according to claim 10 , wherein said bit number q is 4.
16 . the information processing unit according to claim 10 , wherein said first memory element and said second memory element are latch circuits.
17 . The information processing unit according to claim 10 , wherein said third memory element, said fourth memory element and said fifth memory element are shift registers.