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.
Programming Praxis 
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