2022-09-01

The Goldilocks Field

The field of prime order:

p = 2^{64} - 2^{32} + 1

has some nice properties for ZK proofs, notably STARKs.

The order of $\mathbb{F}_p^*$ is $p - 1$ , which is equal to:

2^{64} - 2^{32} = 2^{32} \cdot 3 \cdot 5 \cdot 17 \cdot 257 \cdot 65537

This means that the field has a $2^{32}$ th root of unity, which is very useful.

$\mathbb{F}_p^*$ is generated by:

g = 7

And taking $g^{(p - 1) / 2^{32}}$ gives us our root of unity:

\omega = \texttt{0x185629dcda58878c}

Extensions

$x^2 + 7$ is an irreducible polynomial of degree 2 in $\mathbb{F}_p[x]$

$x^3 + 3$ is an irreducible polynomial of degree 3 in $\mathbb{F}_p[x]$

We can use these to define $\text{GF}(p^2)$ and $\text{GF}(p^3)$ , respectively, giving us fields of size $\text{128}$ and $\text{192}$ bits.

Shotouts to @mjos_crypto for finding a smaller root of unity:

\omega = 20033703337