Modular arithmetic apparatus and method having high-speed base conversion function
AssigneeKabushiki Kaisha Toshiba
InventorShinichi Kawamura
Life of this patent
Estimating the term…
Abstract
In a modular arithmetic apparatus including a plurality of product-sum circuits having a modular arithmetic function and parallelly arranged, and a correction term calculation unit for calculating a correction term to be used for modular arithmetic operation in the product-sum circuits, the correction term calculation unit sequentially calculates the correction term in units of bits, and each of the product-sum circuits sequentially reflects the correction term calculated by the correction term calculation unit and performs base conversion or base extension.
Claims19
A modular arithmetic apparatus for executing a predetermined arithmetic algorithm in a residue number system, comprising:
- a plurality of arithmetic units configured to receive a plurality of base elements and calculate one of a base conversion and a base extension of the plurality of base elements to generate a corresponding plurality of converted base elements or extended base elements, wherein each arithmetic unit includes
- a multiplier configured to multiple two input values and produce a multiplied valve,
- an adder configured to add the multiplied value to a register feedback value,
- a register, and
- a switch connecting the register to the adder, said switch controlled by a bit signal and configured to enable or disable the input of a register value into the adder;
- and
- a correction term calculating unit having an accumulator accumulating an input signal and configured to approximate an unknown parameter k for the one of a base conversion or base extension to generate a carry, the carry being generated based on an output of the accumulator and provided to the switch as the bit signal.
A modular arithmetic apparatus for executing a predetermined arithmetic algorithm in a residue number system, comprising:
- a plurality of correction term calculating units configured to approximate a respective unknown parameter k for one of a base conversion or and a base extension to a carry generated by cumulative addition of a previous calculation result;
- a plurality of switching sections, each switching section connected in series to a respective one of said correction term calculating units, each switching section configured to enable/disable calculation of a specific term in the base conversion or base extension in accordance with the respective unknown parameter k output from said one of correction term calculating units;
- a plurality of arithmetic units, each arithmetic unit connected in series to a respective one of said switching sections, each arithmetic unit configured to calculate a base conversion or base extension in units of base elements by performing multiplication, addition, and modular arithmetic operations including the calculation of the specific term;
- and
- a connection unit connecting a first set of devices comprising a respective calculating unit, switching section, and arithmetic unit to another set of devices comprising a respective correction term calculating unit, switching section, and arithmetic unit.
A modular arithmetic method of executing one of base conversion or base extension from a certain base as an input of a plurality of base elements to another base in a predetermined arithmetic algorithm in a residue number system, the method comprising:
- calculating the one of base conversion or base extension in units of base elements by performing multiplication, addition, and modular arithmetic operations including the calculation of a specific term;
- and
- approximating an unknown parameter k for the base conversion or base extension to a carry generated by cumulative addition of a previous calculation result;
- wherein
- said calculating step includes switching between a first mode and a second mode in accordance with the approximated unknown parameter k, and
- said calculating and approximating steps are repeated until a predetermined number of values are calculated.
Dependencies are inferred from the claim text.