Modular arithmetic operation system

A table setup device comprising:

• repeated addition means for adding a modulus to itself repeatedly;
• complement computing means for computing the two's complement of low-order k bits of each sum obtained by said repeated addition means;
• and
• table writing means for writing each sum into a table address corresponding the two's complement of that sum obtained by said complement computing means,
• thereby setting up on a storage device a multiple table in which multiples of said modulus are stored to correspond with low-order predetermined bits of an input number.

A modular multiplication arithmetic unit comprising:

• a split multiplication section for multiplying a multiplier and each of blocks of a predetermined number of bits in a multiplicand and adding a residue to the result of multiplication, said block being taken from said multiplicand in sequence from its low-order side;
• an input register for holding an input number output from said split multiplication section;
• multiple computing means for obtaining a multiple of a modulus corresponding to a low-order predetermined bits of said input number in said input register by table lookup using a table in which arithmetic data has been stored in advance on the basis of said low-order predetermined bits of said input number;
• adder means for performing addition of said multiple of said modulus obtained by said multiple computing means and the contents of said input register, the result of said addition being applied to said split multiplication section as said residue for each addition until said addition is performed a predetermined number of times;
• and
• correcting means for making a correction on the result of addition by said adder means.

A modular arithmetic unit for computing TR.sup.-1 mod N=REDC(T) to obtain T mod N=REDC(T*(R.sup.2 mod N)), the residue of the division of integer T by integer N, comprising:

• an input register for holding an input number T;
• multiple computing means for obtaining a multiple m'N (where m'=(T mod b) N' mod b, N'=integer, R (integer)=b.sup.n, b=2.sup.k) of a modulo N corresponding to a low-order predetermined bits of said input number T in said input register by table lookup using a table in which arithmetic data have been stored in advance on the basis of said low-order predetermined bits of said input number;
• adder means for performing addition of said multiple m'N of said modulo N obtained by said multiple computing means and the contents of said input register and updating the contents of said input register with high-order predetermined bits of the result of said addition for each addition until said addition is performed a predetermined number of times, thereby outputting t=(T+mN)/R;
• and
• correcting means for making a correction on the result t of addition by said adder means such that if t<N, t=REDC(T), and if t.gtoreq.N, t-N=REDC(T), thereby obtaining TR.sup.-1 mod N.