About Finite Fields
RISC Zero's computational receipts are built by converting an assertion of computational integrity into an assertion about polynomials over finite fields. This document serves as a minimal introduction to finite fields, targeted at folks who have some exposure to modular arithmetic and who are curious to learn more about the math and cryptography behind RISC Zero.
Finite Fields 101: Reciprocals, Exponents, and Generators
Loosely speaking, a field is a set of elements for which addition, subtraction, multiplication, and division work cleanly.
Here's what we mean by division working cleanly: for any field element , we should be able to find a field element such that We call the reciprocal of or the multiplicative inverse of .
Example: The integers are not a field because the reciprocal of 3 is not an integer.
Example: The integers modulo 5 are a field. In this field, the reciprocal of 2 is 3. 4 is its own reciprocal.
If is prime, the integers modulo are a field. Moreover, I can find some element and write all the integers modulo as powers of .
Example: The integers modulo 5 can all be written as a power of 3.
We say is a multiplicative generator for the integers modulo 5. For any prime modulus, a multiplicative generator exists.
Finite Fields 201: Polynomials over Finite Fields
Most of your Algebra II knowledge about polynomials still holds in finite fields.
. Observe that
has roots at 1 and 4, and we can factor in the familiar way:
Given three ordered pairs modulo 5, we can interpolate a degree 2 polynomial that passes through each point.
FFTs still work over finite fields, although they're called NTTs.
If the ideas above this text make sense, you should have enough finite field background to make sense of the applications in RISC Zero.
Finite Fields 301 - Roots of Unity
is called an Root of Unity if .
Example: 3 is a 4th root of unity modulo 5.
Roots of unity come up constantly in a wide variety of applications: you'll most frequently see the root of unity written as , and they come up so frequently because they give an easy way to describe rotations. This is what Euler's Formula is about.
Example: Multiplying by
is a rotation of order 4 in
. More generally, multiplying by a 4th root of unity is a rotation of order 4.