A method of rapid RSA key generation

This paper improves a method for key generation of RSA public key cryptosystems. In order to construct an RSA public key cryptosystem, it is necessary to generate strong keys using primes which are tolerable against a ‘p±1 factorizing attack’. Conventionally, J. Gordon has developed a method for generating such primes by sieving multiples of primes smaller than eight bits and employing high order exponential calculation, which has resulted in a long computing time. This method improves Gordon’s method by sieving multiplies of primes smaller than 32 bits and utilizing the Chinese remainder theorem to avoid such a high order exponential calculation. Consequently, the RSA key is generated in a practical time of on average four minutes with 32 bits work station Hitachi 2050/32. [In Japanese.]