Field Extensions
\gdef\p#1{\left({#1}\right)} \gdef\norm#1{\left|{#1}\right|} \gdef\F{\mathbb{F}} \gdef\i{\mathrm{i}} \gdef\j{\mathrm{j}} \gdef\om{\mathrm{\omega}}
Given a prime field \F_p with p = 2^{31} - 1. Because p is a Mersenne prime, it can be implemented particularly efficiently. It also neatly fits into a 32-bit integer allowing fast SIMD and GPU implementations and efficient use of memory.
While fast, this field has two downsides: it does not support efficient NTTs and it is not large enough to effectively use the Schwartz-Zippel lemma. We can address both by constructing a larger field extension.
The smallest generator of the multiplicative group is 7, with order
\norm{\F_p^\times} = 2 \cdot 3^2 \cdot 7 \cdot 11 \cdot 31 \cdot 151 \cdot 331
The size of the field is almost 31-bits:
\log_2 \norm{\F_p} \approx 31 - 6.7\cdot10^{-10}
Complex Extension
Note that -1 is not a square if \F_p and thus X^2 + 1 is irreducible over \F_p. We can thus construct \F_{p^2} by the extension \F_p[X]/(X^2 + 1). Because of analogy with complex numbers, we will call the root \i and for a + b \cdot \i we cann a the real and b the imaginary component.
The complex extension has a generator 12 + \i with order
\norm{\F_{p^2}^\times} = 2^{32} \cdot 3^2 \cdot 7 \cdot 11 \cdot 31 \cdot 151 \cdot 331
So we can now efficiently perform NTTs up to size 2^{32}, larger than \F_p itself! If we are ambitious, we can also implement 3^2, and use Rader's NTT to 7 to 2 \cdot 3.
Note that the 8-th roots of unity have nice structure:
\{ \pm 1, \pm i, \pm 2^{15} \pm 2^{15}\cdot\i \}
The Frobenius endomorphism is given in coefficient form by the map
\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}
which is also known as complex conjugation.
Larger extensions
The complex extension is still not large enough for some cryptographic purposes:
\log_2 \norm{\F_p} \approx 62 - 1.34\cdot10^{-9}
With a target security of about 128 bits, we need to look at a degree 4, 5 or 6 extension. We elliminate 5 as it does not have F_{p^2} as a subfield. The degree 4 extension is slightly under our security target, and in practice we actually need some overhead. So we look at the degree 6 extension.
Let's construct \F_{p^6} as a cubic extension over \F_{p^2}, some low Hamming weight cubic non-roots in \F_{p^2} are 5, 1 + 2 \cdot \i, 2 + \i, \dots. Let's pick the irriducible polynomial X^3 - 5 and construct \F_{p^2}[X]/(X^3 - 5). We'll write the new cube root of 5 as \j with \j^3 = 5 so we now have values a + b \cdot \j + c \cdot \j^2 where a, b, c themselves are complex.
\begin{bmatrix} 1 & 0 & 0 \\ 0 & \om_3 & 0 \\ 0 & 0 & \om_3^2 \end{bmatrix}
Where \om_3 = 1513477735. Together with conjugation, these generate the six elements of the automorphism group of \F_{p^6}.
Dot products
We are interested in computing dot product over the vector space \F_p^n. We want to do this by efficiently representing the vector space using elements of \F_{p^6}.
Observe that \F_{p^2} can be seen as an algebra over the vector space \F_p^2. Equiped with a bilinear operator
(a_0 + a_1 \cdot \i) \cdot (b_0 + b_1 \cdot \i) = (a_0 \cdot b_0 - a_1 \cdot b_1) + (a_0 \cdot b_1 + a_1 \cdot b_0) \cdot \i
Observe that the constant term is almost a dot product of the vectors (a_0, a_1) and (b_0, b_1). To fix it we only need to flip the sign on a_1 or b_1.
Observe that \F_{p^6} can be seen as an algebra over the vector space \F_{p^2}^3.
\begin{aligned} (a_0 + a_1 \cdot j + a_2 \cdot \j^2) \cdot (b_0 + b_1 \cdot j + b_2 \cdot \j^2) = &\\ (a_0 \cdot b_0 + 5 \cdot a_1 \cdot b_2 + 5 \cdot a_2 \cdot b_1) +& \\ (a_0 \cdot b_1 + a_1 \cdot b_0 + 5 \cdot a_2 \cdot b_2) \cdot \j +& \\ (a_0 \cdot b_2 + a_1 \cdot b_1 + a_2 \cdot b_0) \cdot \j^2 \end{aligned}
Extension
When we create an extension \F[X]/(f) with some polynomial f(X), we artificially create an element \alpha that is a root of f, i.e. f(\alpha) = 0 by decree.
If we have a different field of same degree, but with a different polynomial g then this will have a different artificial root \beta such that g(\beta) = 0.
From ??? theorem it follows that these fields are isomorphic. That means there are functions between them such that:
- \phi(a + b) = \phi(a) + \phi(b)
- \phi(a \cdot b) = \phi(a) \cdot \phi(b)
From this it follows that \phi preserves the identity elements 0, 1.
It also follows that for c \in \F_p \phi(c \cdot a) = c \cdot \phi(a).
\phi(c) = c
\phi(0) = \phi(0 + 0) = \phi(0) + \phi(0)
From this it follows that \phi(\alpha) is a root of f in \F_\beta. There are exactly n such roots. When we pick such a root, \phi is fully specified.
Field Isomorphisms
Definition 1. A field isomorphism is a bijective function between two fields A, B such that for a, b \in A:
\begin{aligned} \phi(a + b) &= \phi(a) + \phi(b) \\ \phi(a \cdot b) &= \phi(a) \cdot \phi(b) \end{aligned}
Lemma 1. If \phi is a field isomorphism, then \phi^{-1} is too.
Proof: We need to proof \phi^{-1}(a + b) = \phi^{-1}(a) + \phi^{-1}(b), substitute this back into the relation for \phi and apply \phi^{-1} to both sides: \begin{aligned} \phi(\phi^{-1}(a) + \phi^{-1}(b)) &= \phi(\phi^{-1}(a)) + \phi(\phi^{-1}(b)) \\ \phi(\phi^{-1}(a) + \phi^{-1}(b)) &= a + b \\ \phi^{-1}\p{\phi(\phi^{-1}(a) + \phi^{-1}(b))} &= \phi^{-1}\p{a + b} \\ \phi^{-1}(a) + \phi^{-1}(b) &= \phi^{-1}\p{a + b} \\ \end{aligned} Similarly for multiplication.
Lemma 2. Field isomorphism perserve 0 and 1. Given fields A, B and an isomorphism \phi: A \to B we have \begin{aligned} \phi(0_A) &= 0_B \\ \phi(1_A) &= 1_B \end{aligned}
Proof: Consider \begin{aligned} \phi(0_A) &= \phi(0_A + 0_A) \\ &= \phi(0_A) + \phi(0_A) \end{aligned} Subtracting \phi(0_A) from both sides we obtain 0_B = \phi(0_A). Now consider \begin{aligned} \phi(1_A) &= \phi(1_A \cdot 1_A) \\ &= \phi(1_A) \cdot \phi(1_A) \\ 0_B &= \phi(1_A) \cdot (1_B - \phi(1_A)) \end{aligned} The two solutions are \phi(1_A) = 0_B and \phi(1_A) = 1_B. If A and B are non-trivial then 0_B \neq 1_B and the first solution is not possible because \phi is bijective and the preimage of 0_B is 0_A. Therefore, \phi(1_A) = 1_B.
Lemma 3. Isomorphism perserves the base field, for n \in \F_p, we have \phi(n_A) = n_B.
Proof: This follows from 1 generating the prime order subfield: \phi(n_A) = \phi\p{\sum_{i\in[0,n)} 1_A} =\sum_{i\in[0,n)} \phi(1_A) = \sum_{i\in[0,n)} 1_B = n_B
Lemma 4. Field isomorphisms are vector space isomorphisms.
Given a basis, vector space isomorphism are represented by invertible matrices.
Lemma 5. The isomorphism is fully specified by the map of the extension generator, and there are exactly n isomorphisms.
Definition 2. A field automorphism is a field isomorphism from A onto itself.
Lemma 6. The Frobenius map x \mapsto x^p is a field automorphism.
Lemma 6. The Frobenius map generates all n field automorphisms.
References
- [Len91] H. Lenstra (1991). Finding isomorphism between finite fields. [Len91]: https://people.tamu.edu/~rojas//lenstraFq.pdf
https://arxiv.org/abs/math/9204234
https://www.math.u-bordeaux.fr/~ballombe/fpisom.ps
