Patent ID: 7010560

Claim:
A modular arithmetic apparatus for performing an arithmetic operation of an integer on a basis of a residue number system (RNS), comprising: an input/output unit configured to input data included in modulus p and to output an arithmetic result; a storage unit configured to store at least a portion of a plurality of base parameter sets, each base parameter set including a set of base parameters indicating base elements, each one of said plurality of base parameter sets containing a different number of base parameters; a base selection unit configured to select one base parameter set in said storage unit according to the modulus p input from said input/output unit; and a plurality of arithmetic units configured to perform operations in parallel according to the selected one base parameter set to obtain the arithmetic result, wherein the numbers of the base parameters of each base parameter set in said storage unit are multiples of {u−t, u−t+1, - - - , u}, respectively, said u is a number of the arithmetic units and said t is a maximum integer of a number of unused ones of the arithmetic units (t=0 or 0<t<u).