Opening Non-Prime Fields
Non-Prime Fields
- Length
- 21 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Finite fields of prime-power size come from univariate polynomials over a field of prime size . O'Donnell starts from the polynomial ring, which shares division with remainder and Euclid's algorithm with the integers, and defines irreducible polynomials by analogy with primes. Reducing modulo an irreducible of degree yields a field of size , with arithmetic carried out as polynomial arithmetic. A prime number theorem for irreducibles puts the chance that a random degree- polynomial is irreducible between and . Shoup's deterministic algorithm, polynomial in and , closes lecture 10c of CMU 15-750: A Theorist's Toolkit, alongside Berlekamp's randomized factoring and van Lint's explicit irreducibles.

Your comment is kept while you sign up.Sign in
Builds fields of size from polynomials modulo an irreducible and counts how often irreducibles occur.
Finite fields of prime-power size come from univariate polynomials over a field of prime size . O'Donnell starts from the polynomial ring, which shares division with remainder and Euclid's algorithm with the integers, and defines irreducible polynomials by analogy with primes. Reducing modulo an irreducible of degree yields a field of size , with arithmetic carried out as polynomial arithmetic. A prime number theorem for irreducibles puts the chance that a random degree- polynomial is irreducible between and . Shoup's deterministic algorithm, polynomial in and , closes lecture 10c of CMU 15-750: A Theorist's Toolkit, alongside Berlekamp's randomized factoring and van Lint's explicit irreducibles.
This lecture
Lecture 28 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.