Patent ID: 6175850
Filing Date: 2001-01-16
Classification: G06F

Abstract:
A method for carrying out a basic operation of a public key cryptosystem using modular calculations based on a redundant binary calculation scheme, including a modular reduction a mod c where a is a dividend and c is a divisor, comprising the steps of:(a) registering the dividend a and the divisor c in a dividend register and a divisor register, respectively;(b) left shifting the divisor c in the divisor register by (i-j) digits when a number of digits j of the divisor c is less than a number of digits i that can be stored in the divisor register;(c) calculating the modular reduction a mod c up to (i-j)-th decimal place using the dividend a in the dividend register and the divisor c in the divisor register as left shifted by the step (b), to obtain a remainder as a modular reduction result; and(d) carrying out the basic operation of the public key cryptosystem using the modular reduction result obtained by the step (c).