Generating Prime Numbers Using Genetic Algorithms

Abstract

Genetic algorithms are well-known and frequently used heuristic methods for solving optimization problems. In modern cryptography the generation of large primes has an important role in the implementation of public-key cryptosystems such as RSA. In general the prime number generation starts from the random number. If the generated random number can pass a specified probabilistic primality test the random number is tentatively considered as a prime number and applied to a public-key cryptosystem. This paper investigates the application of genetic algorithms for generating large prime numbers that have special significance in cryptography. An introduction to the theory of prime numbers and the methods used to check the primality of a large number are shown. Moreover the implementation of a genetic algorithm for generating prime numbers with a convenient representation and genetic operators is presented. We compare the efficiency of the existing method for generating prime numbers and genetic algorithms techniques and we show that GA can be a viable option to generate large prime numbers.