Generating Large Random Primes with the Miller-Rabin Primality Test

[@andrecarvalho8679]

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

[@JacksonInfoSec]

Glad it was helpful!

[@johnteran8889]

superb video. thanks so much!

[@JacksonInfoSec]

Thanks man, appreciate the support.

[@lennemo99]

incredibly helpful video thank you

[@JacksonInfoSec]

Thank you for your comment. I am glad it helped.

[@alagaika8515]

Got some goosebumps when seeing an indentation of two spaces 😜

[@JacksonInfoSec]

Ha-ha, is that a Python faux pas?

[@zanti4132]

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?