Skip to main content

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 xx, we should be able to find a field element x−1x^{-1} such that x⋅x−1≡1.x\cdot x^{-1}\equiv1. We call x−1x^{-1} the reciprocal of xx or the multiplicative inverse of xx.

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 pp is prime, the integers modulo pp are a field. Moreover, I can find some element gg and write all the integers modulo pp as powers of gg.

Example: The integers modulo 5 can all be written as a power of 3.

We say 33 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.

Example: Consider f(x)=x2−1 mod 5f(x)=x^2-1\text{ mod }5. Observe that f(1)=f(4)=0.f(1)=f(4)=0. We say ff has roots at 1 and 4, and we can factor in the familiar way: f(x)=(x−1)(x−4)f(x)=(x-1)(x-4).

Example: 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​

zz is called an nthn^{th} Root of Unity if zn=1z^n=1.

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 nthn^{th} root of unity written as e2πine^\frac{2\pi i}{n}, 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 ii is a rotation of order 4 in C\mathbb{C}. More generally, multiplying by a 4th root of unity is a rotation of order 4.

Additional References:​