Generate a Random Prime Number in Python [Various Methods]

Generating a random prime number is a task I’ve encountered frequently over the last decade, especially when building secure backends or working on data encryption.

While Python doesn’t have a single “magic button” in the standard library for this, there are several efficient ways to get it done.

In this tutorial, I will show you exactly how I generate random primes using different libraries, depending on whether you need speed or cryptographic security.

Why You Might Need a Random Prime

In my experience, the most common reason to generate these numbers is for RSA encryption or creating unique identifiers for secure transactions.

If you are working on a fintech application, perhaps calculating interest rates for a New York-based bank, ensuring these primes are truly random is critical.

Let’s get into the various methods I use in my day-to-day development.

Method 1: Use the secrets and math Modules

If you want to stay within the Python standard library, this is the easiest approach I’ve found.

I use the secrets module because it is cryptographically secure, unlike the standard random module.

Here is the logic I follow: I generate a random odd number and then check if it is prime using a primality test.

import secrets
import math

def is_prime(n):
    if n < 2: 
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def generate_random_prime(lower, upper):
    while True:
        # I pick a random number in the range
        num = secrets.randbelow(upper - lower) + lower
        if is_prime(num):
            return num

# Example: Generating a prime for a secure ZIP code ID in Beverly Hills (90210)
print(f"Random Prime: {generate_random_prime(10000, 99999)}")

You can see the output in the screenshot below.

In this code, I use secrets.randbelow() to ensure the number is unpredictable. This is vital if you are handling sensitive user data.

Method 2: Use the PyCryptodome Library (The Pro Way)

When I’m working on a production-grade security feature, I rarely write my own primality test. Instead, I rely on PyCryptodome.

It features a highly optimized getPrime function that is incredibly fast at generating large primes used in American cybersecurity standards.

You’ll need to install it first:

pip install pycryptodome

Here is how I implement it:

from Crypto.Util import number

def get_large_prime(bits):
    # This generates a random prime with a specific bit length
    return number.getPrime(bits)

# I often use 1024 or 2048 bits for encryption keys
prime_key = get_large_prime(1024)
print(f"Your Secure Large Prime: {prime_key}")

You can see the output in the screenshot below.

I love this method because it handles the heavy lifting of the Miller-Rabin primality test for me. It’s my go-to for high-performance apps.

Method 3: Use the SymPy Library

Sometimes, I’m working more on the data science side of things rather than pure security. In those cases, I prefer using SymPy.

SymPy is a symbolic mathematics library that has a very convenient randprime function.

Install it using:

pip install sympy

Here is the script I use:

from sympy import randprime

def generate_sympy_prime(start, end):
    # This finds a random prime between start and end
    return randprime(start, end)

# Example: Finding a prime number for a statistical study on US Census data
population_sample_prime = generate_sympy_prime(100000, 1000000)
print(f"SymPy Generated Prime: {population_sample_prime}")

You can see the output in the screenshot below.

The randprime function is great because it is readable and behaves exactly like the random.randint function we are all used to.

Method 4: The Sieve of Eratosthenes (For Small Ranges)

If I need to generate multiple random primes within a small, fixed range, say, for a lottery simulation in Florida, I use a Sieve.

The Sieve of Eratosthenes is an ancient but brilliant algorithm that I still find useful today for its efficiency in small ranges.

import random

def sieve_of_eratosthenes(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    for p in range(2, limit + 1):
        if is_prime[p]:
            primes.append(p)
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
    return primes

# I generate all primes up to 1000 and pick one randomly
all_primes = sieve_of_eratosthenes(1000)
random_choice = random.choice(all_primes)

print(f"Random Prime from Sieve: {random_choice}")

You can see the output in the screenshot below.

I find this method works best when you need to pick primes repeatedly from the same set of numbers without recalculating them every time.

Method 5: Use the Miller-Rabin Primality Test

For those of you who want to understand the “under the hood” mechanics, I often recommend implementing the Miller-Rabin test.

This is a probabilistic test that is much faster than checking every factor, especially for huge numbers like US national debt figures!

import secrets

def is_miller_rabin_prime(n, k=5): # k is the number of tests
    if n <= 1: return False
    if n <= 3: return True
    if n % 2 == 0: return False

    # Write n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    for _ in range(k):
        a = secrets.randbelow(n - 4) + 2
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def generate_huge_prime(bits=128):
    while True:
        # Generate a random n-bit number
        p = secrets.randbits(bits)
        # Ensure it is odd and has the correct bit length
        p |= (1 << (bits - 1)) | 1
        if is_miller_rabin_prime(p):
            return p

print(f"Huge Miller-Rabin Prime: {generate_huge_prime(256)}")

In my experience, this is the most educational way to handle primes. It gives you total control over the accuracy vs. speed trade-off.

Key Considerations for Prime Generation

When choosing between these methods, I usually ask myself two questions: “How big is the number?” and “Does it need to be secure?”

For simple scripts or academic purposes, the math or SymPy methods are perfect and easy to read.

However, if you are building an app for the US market where data privacy is regulated, always stick with secrets or PyCryptodome.

Another thing I’ve noticed is that generating very large primes (over 4096 bits) can be slow on standard hardware.

In those cases, I always pre-filter my numbers by checking if they are divisible by small primes (like 3, 5, 7, and 11) before running the Miller-Rabin test.

Comparison Table: Which Method Should You Use?

I hope this tutorial helped you understand how to generate random prime numbers in Python.

In this article, I covered five different ways to achieve this, from simple built-in solutions to professional-grade cryptographic libraries.

Yoy may also like to read:

• How to read video frames in Python
• How to Check Python Version
• What Does // Mean in Python? (Floor Division with Examples)
• Understand __init__ Method in Python

Bijay Kumar

I am Bijay Kumar, a Microsoft MVP in SharePoint. Apart from SharePoint, I started working on Python, Machine learning, and artificial intelligence for the last 5 years. During this time I got expertise in various Python libraries also like Tkinter, Pandas, NumPy, Turtle, Django, Matplotlib, Tensorflow, Scipy, Scikit-Learn, etc… for various clients in the United States, Canada, the United Kingdom, Australia, New Zealand, etc. Check out my profile.

enjoysharepoint.com/