We may need to generate a large random prime number in Python for various reasons. When we generate RSA keys, the module internally generates two large prime numbers from which the RSA private key and the public key are generated. When we need to generate a large random prime number for cryptographic purposes, we need to ensure that the prime number is random enough (What is entropy in cryptography?)

In our previous article, we discussed how to generate a random number for cryptographic purposes. In this article, we would discuss how to generate a large random prime number that is secure enough for cryptographic purposes.

How to generate a prime number in Python?

Firstly, we would try a simple approach to generate a prime number in Python. And then we would discuss why this method is not good for generating a large prime number.

We know that a prime number is divisible only by 1 and the number itself. So, if we take a number and try to divide it by numbers less than the number itself, we would get all its factors. And, when the generated number has only two factors, we know that the number is a prime number.

So, let’s try to generate all prime numbers using this method. We would take a number n and then try to divide n by i where i < n. In fact, we do not need to divide n by all i < n. We can divide n by all i < n that are prime numbers. In other words, we can divide n by all prime numbers less than n. But, if a number has two factors and one of the factors is more than sqrt(n), then the other factor is definitely going to be less than sqrt(n). So, we do not need to divide n by all primes less than n. We can divide n by all prime numbers that are less than sqrt(n). If we get a factor of n that is not 1 or n, then we know that n is a composite number.

So, let’s try to use this logic to generate the first 1000 prime numbers. We would start with 2. As 2 is a prime number, we would add 2 to a list. Then we would increment the number by 1 and check its prime factors. If the number is prime, we would add the number to the list of prime numbers. And, when we would check the prime factors of a number, we would take the prime numbers from the generated list.

import math
import secrets

def isPrime(number, primes):

    root = math.sqrt(number)
    for i in range(len(primes)):
        if(primes[i] > root):
            return True
        if(number % primes[i] == 0):
            return False


primes = list()
primes.append(2)
i = 1
ITERATION = 100

for j in range(1000):
    i += 2
    if(isPrime(i, primes)):
        primes.append(i)
print("All prime numbers are generated")

If we run the program, we would see the program can generate 100,000 prime numbers very easily using a standard desktop computer. But, let’s say we want to generate 2048-bit RSA keys for which we need 2 1024-bit random prime numbers. One way to do so is to generate a 1024-bit random number and then check its primality using the above method. But, that would be very slow. So, we need some efficient method to generate a large random prime number.