## 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.

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 = *SIEVE_SIZE
for p in prs:
offset = (-(base + p) // 2) % p
sieve[offset::p] =  * 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
```