Patent ID: 7248692

Claim:
A method of determining a pair of numbers comprising a first number and a second number, the second number being the multiplicative inverse with respect to a modulus of the first number, said modulus being equal to the product of a first prime number and a second prime number, said method comprising the steps of: selecting the first number; computing a first subnumber for the second number as a multiplicative inverse of the first number with respect to a first sub-modulus that is equal to the first prime number minus 1 divided by the greatest common divisor of the first prime number minus 1 and the second prime number minus 1; computing a second subnumber for the second number a multiplicative inverse of the first number with respect to a second sub-modulus that is equal to the second prime number minus 1, with said first sub-modulus and said second sub-modulus being relatively prime; determining the second number using the first sub-number and the second sub-number by means of the Chinese remainder theorem; storing the second number as a private key; and outputting at least one of the first and second numbers for use as a key in a cryptosystem.