Generating Large Random Primes with the Miller-Rabin Primality Test

In this video we talk about how to generate random probable prime numbers with a specified bit length using the Miller-Rabin primality test. We also discuss the average gap lengths between consecutive primes in that bit range. We implement the concepts in Python.

Code:

[andrecarvalho]

Thank you this video was extremly helpfull to understand some key concepts!

[alagaika]

Got some goosebumps when seeing an indentation of two spaces 😜

[zanti]

Regarding the number of tests you are likely to have to make before you find a probable prime, that actually follows from the Prime Number Theorem, a very important theorem in Number Theory. From this theorem, if n is a randomly chosen positive integer, then the probability n is prime is 1/ln(n), where ln(n) is the natural logarithm of n. From this it follows that the average gap between prime numbers is ln(n). As you are testing only odd integers, the number of tests needed will be on average half that, i.e. ln(n)/2.

To give a concrete example, if n is created as in your video using 100 randomly assigned binary digits, then you'll get a number between 2⁹⁹ and 2¹⁰⁰, which is roughly 10³⁰. The average gap should be about 30 × ln(10). That is about 69, so it should take 34 or 35 tests on average to get a hit. Even with 1000 binary digits - that would be a number with over 300 digits when written in decimal - the number of tests on average should be around 350.

[allurbase]

Thank you, any fast way of producing false positives for Miller-Rabin?