Generating Large Random Primes

June 9, 2017

We studied Pocklington’s Criterion, which lets us quickly find large random primes, in a previous exercise. That algorithm generates a certified prime — a number that is proven to be prime — rather than a probable prime according to some pseudoprimality test.

Even though it’s not hard to generate a certified large prime, most cryptographic applications accept probable primes, primarily because it is much faster to generate a probable prime than a certified prime. Wikipedia explains the algorithm:

For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly chosen range of odd numbers of the desired size is sieved against a number of relatively small primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard probabilistic primality test such as the Baillie-PSW primality test or the Miller-Rabin primality test for probable primes.

Your task is to write a program that implements the Wikipedia algorithm for generating large random probable primes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

One Response to “Generating Large Random Primes”

  1. Paul said

    In Python.

    SIEVE_SIZE = 50000
    prs = list(primes(65000))[1:]
    
    def large_prime(lo, hi):
        while True:
            base = random.randrange(lo, hi - 2*SIEVE_SIZE) | 1
            sieve = [1]*SIEVE_SIZE
            for p in prs:
                offset = (-(base + p) // 2) % p
                sieve[offset::p] = [0] * len(range(offset, SIEVE_SIZE, p))
            for i, f in enumerate(sieve):
                if f:
                    cand = base + 2 * i
                    if is_prime(cand):  # miller-rabin
                        return cand
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: