Efficient Generation of Primes and Safe Primes

Abstract

Generating large primes and safe primes is important to enhance the security of public-key cryptosystem such as RSA, ElGamal, and DSS. Because generating large primes and safe primes takes long time and requires a lot of resources, we need to generate them efficiently. Prime generation and safe prime generation consists of a random number generation and primality tests. The primality test is much more time-consuming than the random number generation. Therefore, these primality tests are combined to reduce the running time. Trial division and Miller-Rabin combination test is widely used. Maurer et al. analyzed trial division and Miller-Rabin combination test very accurately. Joye et al. introduced JPV prime generation that reduces the number of generating random numbers. However, the performance of primality test depends on the performance each device. For example, in PC, the combination of PGCD test and Miller-Rabin combination test is slower than others while the test is faster than others in Galaxy Tab. Therefore, it is necessary to research on which primality test more time-efficient is and what the fastest running time is. To solve these problems, we probabilistically analyzed primality tests using GCD and division table. We expected the running time of them and the number of primes which makes the running time fastest. PGCD and Miller-Rabin combination test uses PGCD test that calculates the greatest common divisor of a random number r and Πk to check whether they are relatively prime when Πk is the product of k primes. Trial division checks divisibility of r with one prime at a time while PGCD test does it with k primes at a time. Therefore, we analyzed the running time of PGCD test in detail. Also, we proposed MGCD test that enhances PGCD test. MGCD test divides Πk into b-bits and checks whether they are relatively prime. A combination of division table and Miller-Rabin test uses incremental number generation that generates the first random number after that it generates random numbers by adding a constant to the first random number. Incremental number generation is faster than random number generation and can find all random numbers that are divided by each prime. We analyzed the probability of finding a prime depending on the size of table in detail. The experiment performed both in PC and Galaxy Tab and compared the expected running time and the measured running time of each test. The experimental result shows our analysis is good because the error rate is less than 3%. The combination of division table and Miller-Rabin test is faster than all other tests. The difference of running time between the other tests are not significant. We expect that the combination of division table and Miller-Rabin test is faster in other devices because which combination test is the faster depends on which operation is faster among division, PGCD, MGCD, and memory access. We probabilistically analyzed combined primality tests and expected the running time of them. Therefore, we proposed the method to determine a proper primality test for each device with only measuring the running time of simple operations.