Miller-Rabin Primality Test in Python 🔍

The Miller-Rabin primality test: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

A python implementation of the probabilistic Miller-Rabin primality test. This test runs in polynomial time O(k polylog(p)) and has a negligible probability of failure 4^(-k), making it suitable for cryptographic applications.

This video builds up from Fermat's primality test. Watch my previous video where I explain it: https://www.youtube.com/watch?v=qDakpCEW5-0

Euclid's lemma: https://en.wikipedia.org/wiki/Euclid%27s_lemma

Fermat's little theorem: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Soup's number theory book: http://www.shoup.net/ntb/ntb-v2.pdf

If you enjoyed this video, please 👍 and +Subscribe. This is one of my first videos. Please leave feedback about what you think I can improve and what other topics you would like to see.

I've just created a Patreon where you can buy me a cup of coffee. Thanks so much for supporting me! https://www.patreon.com/dionyziz