Opening Primes and Prime Fields
Primes and Prime Fields
- Length
- 16 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Integers mod p
The integers modulo a prime form a field, and O'Donnell proves it by computing reciprocals with the extended Euclidean algorithm in polylogarithmic time. Fermat's little theorem offers a second route to inverses, and integer GCD proves hard to parallelize. No fast deterministic method is known for finding an -bit prime, so random numbers are sampled and each is tested, for instance with the AKS test. The Prime Number Theorem bounds prime density, which makes the search efficient. A nine-element field, built by adjoining a square root of to the integers mod 3, closes this session of Carnegie Mellon's graduate course A Theorist's Toolkit.
Your comment is kept while you sign up.Sign in
Inverts elements mod by extended Euclid, then finds -bit primes by random sampling and primality testing.
The integers modulo a prime form a field, and O'Donnell proves it by computing reciprocals with the extended Euclidean algorithm in polylogarithmic time. Fermat's little theorem offers a second route to inverses, and integer GCD proves hard to parallelize. No fast deterministic method is known for finding an -bit prime, so random numbers are sampled and each is tested, for instance with the AKS test. The Prime Number Theorem bounds prime density, which makes the search efficient. A nine-element field, built by adjoining a square root of to the integers mod 3, closes this session of Carnegie Mellon's graduate course A Theorist's Toolkit.
AKS primality test
AKS'02
This lecture
Lecture 27 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.