摘要 |
PROBLEM TO BE SOLVED: To handle an arbitrary rule polynomial, to reduce a required memory size and to improve processing efficiency in a polynomial remainder system arithmetic device. SOLUTION: The device is provided with a plurality of arithmetic units 10<SB>1</SB>to 10<SB>n</SB>having a polynomial remainder arithmetic function on GF(2) based on each element f<SB>i</SB>,g<SB>i</SB>(where i=1 to n) of the bases of a polynomial remainder arithmetic system. When m dimensional agreement polynomial N(x) on GF(2) and polynomials a(x) and b(x) on an equal to or less than m dimensional GF(2) are inputted into the units, remainder operations at the base elements f<SB>i</SB>, g<SB>i</SB>for input contents N(x), a(x) and b(x) are executed in parallel at the units and a Montgomery multiplication a(x)b(x)G(x)<SP>-1</SP>mod N(x) is computed uning G(x)=g<SB>1</SB>(x)g<SB>2</SB>(x) to g<SB>n</SB>(x). Thus, parallel computations are executed by the arithmetic units employing polynomial remainder system expression without using a multiple table which normally requires a memory size and without conducting computations for conventional polynomial expression. Moreover, the parallel computations use a Montgomery multiplication. COPYRIGHT: (C)2004,JPO
|