| 摘要 |
PROBLEM TO BE SOLVED: To provide a multiplication remainder operation method and an arithmetic unit that shorten operation time by reducing the number of times of multiplication and addition, eliminate restriction in an input value, enable remainder operation exceeding the maximum bit length where the operation of multipliers/adders to be used can be made, and do not depend on a Montgomery method. SOLUTION: In the case of N=2<SP>n</SP>-M and X=α×2<SP>n</SP>+β, the fact that XmodN is equal to (α×M+β)modN is utilized. The solution of n<SP>2+1</SP>modN is set to be b, A×B is set to be X, and the XmodN is converted to (X/2<SP>n+1</SP>×b+Xmod2<SP>n+1</SP>)modN for further converting to (Xn/2<SP>n+1</SP>×b+Xnmod2<SP>n+1</SP>)modN. Until the bit length of the Xn becomes n+1, the operation of Xn/2<SP>n+1</SP>×b+Xnmod2<SP>n+1</SP>is repeated, and Xn-N is obtained, which is set to be the solution of 'A×BmodN'. COPYRIGHT: (C)2004,JPO
|
