An algorithm for generating a pair of special primes

In this paper, a modification is described for an algorithm generating the pair of prime integers p, q such that the integers g = -(p - 1,q - 1) and h = -(pq - 1) are also prime. The primes p, q satisfied this condition are called common g primes. In 2006 M. J. Hinek introduced such primes for the variant of RSA cryptosystem resistant to small private exponent attacks. The original algorithm for generating common primes can be optimized with the modification described here. The optimized algorithm is two times faster in worst case and more times in average. It takes 19 seconds to generate a pair of 512-bit common primes p, q with 384-bit prime g. The modification uses sieving technique which is also mentioned in the paper of M. J. Hinek. Despite the speed up of the algorithm, the generation of common primes still takes much more time than the generation of typical primes used in RSA cryptosystem.

Keywords

Authors

References