Module 02: Rings, Fields, and Polynomials

Adding a second operation opens the door to polynomial algebra and field extensions.

Prerequisites

After completing this module you will:

Distinguish rings from groups and fields by their algebraic properties
Work with polynomial rings over finite fields
Test polynomials for irreducibility over a given field
Construct quotient rings and understand their role in building new algebraic structures

Work through these notebooks in order:

#	Notebook	What You'll Learn
a	What Is a Ring?	Ring axioms, examples, and non-examples
b	Integers mod n as a Ring	Z_n with both addition and multiplication
c	Polynomial Rings	Building and manipulating polynomials over finite fields
d	What Is a Field?	Fields as rings where every nonzero element has an inverse
e	Polynomial Division and Irreducibility	Long division, remainders, and irreducibility tests
f	Quotient Rings	Modding out by an ideal to create new structures

Build these from scratch in rust/src/lib.rs:

#	Function	Description
1	`poly_eval`	Evaluate a polynomial at a given point over a finite field
2	`poly_add`	Add two polynomials coefficient-wise with reduction
3	`poly_mul`	Multiply two polynomials with coefficient reduction
4	`poly_div_rem`	Polynomial long division returning quotient and remainder
5	`is_irreducible_mod_p`	Test whether a polynomial is irreducible over F_p

Run: cargo test -p rings-fields-poly

Try these attacks in the break/ folder:

Factor a "supposedly irreducible" polynomial to break a scheme built on a quotient ring
Find zero divisors in Z_n for composite n and show why Z_n fails to be a field

See where this shows up in practice (in the connect/ folder):

AES uses GF(2^8), where all field arithmetic lives in a polynomial quotient ring
Reed-Solomon error correcting codes rely on polynomial evaluation and interpolation over finite fields