Generation of a random number that is non-divisible by a set of prime numbers

摘要

A random number that is co-prime with a set of prime numbers is generated, without having to calculate the greatest common denominator of the numbers. The value of 1−x^λ(mod π), where x is a randomly generated value and λ is the Carmichael function, is tested to determine whether it is non-zero. If it equals zero, x is chosen as the random number of interest. Otherwise the value for x is updated, and the procedure is repeated. Due to the minimal amount of computation resources required to select x, the process is particularly well suited for generating cryptographic keys in portable electronic devices, such as smart cards.