Fermat's Primality Test Explained 🔍 | Simplify Prime Checking Algorithms

Check my previous video on simpler primality testing algorithms:
https://www.youtube.com/watch?v=LULHTKznczA

Check my previous video on how powmod can be built in polynomial time:
https://www.youtube.com/watch?v=qed48E92qXc

Fermat's primality test: https://en.wikipedia.org/wiki/Fermat_primality_test

Carmichael numbers: https://en.wikipedia.org/wiki/Carmichael_number

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

This is an implementation of Fermat's primality test in Python. The algorithm is polynomial in the size of the input and it works in O(k polylog(p)) where k is the test accuracy parameter and p is the candidate being tested.

Because Fermat's algorithm uses randomness, it is a probabilistic algorithm.

Fermat's test is a flawed algorithm because Carmichael numbers are composite numbers that the test thinks are prime.

Polynomial-time primality testing has many applications in cryptography such as key generation.

If you liked this video, please thumbs up 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