# Probabilistic proof of multiplying two elements from non-prime finite field

I was reading this paper, and there, they use the ring $$\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$$ for all their operations. And that looks like a construction of finite field $$\mathbb{F}_{\large p^{\Large n}}$$ as the quotient ring of the polynomial ring $$\mathbb{Z}_{\large p}[\alpha]$$ modulo the ideal generated by $$\alpha^n+1$$. And in the paper they use $$n=2^{\large k}$$ and $$q-1 = 2n$$, which makes $$\alpha^n+1$$ the cyclotomic polynomial $$\Phi_{\large 2n}(\alpha)$$ (which makes polynomial multiplication more efficient because Chinese remainder theorem? I'm not too sure). I'm just trying to make a toy implementation for learning purposes, so all these optimisation intricacies are a bit beyond the scope for me. Since they used $$p=257$$, I used the simple algorithm that for any $$X, Y, Z \in \mathbb{F}_{\large p^{\Large n}}$$: \begin{align} &&& Z = X \cdot Y = T_{\large 0} \\ \text{Where} &&& T_{\large k} = \begin{cases} x_{\large k}Y + \Big( \alpha \cdot T_{\large k + 1} \mod \alpha^{\large n} + 1 \Big), & \text{if} \ \ k < n-1 \\ x_{\large n-1} Y, & \text{if} \ \ k = n-1 \\ \end{cases} \end{align} which is correct, I think. And its probably not going to take THAT long to compute, right?

But then I am thinking, since any element $$X \in \mathbb{F}_{\large p^{\Large n}}$$ can be thought of as a polynomial, can you "evaluate" that polynomial at some point $$s \in \mathbb{F}_{\large p}$$? I mean obviously you can in the sense that you can just compute $$X(s)$$: $$\mathbb{Z}_{\large p} \ni X(s) = {\sum_{\large k=0}^{\large n-1} x_{\large k} \cdot s^{\large k}} \mod p$$ but my question is whether doing so is "correct"? Or is this just nonsense gibberish that doesn't map onto anything. The reason I wanna know is because this lemma allows for proving (probabilistically) that a polynomial multiplication $$C = A \cdot B$$ was performed correctly, by picking some random $$p$$ and checking if $$C(p) = A(p) \cdot B(p)$$, over and over again.

And I am wondering if that lemma can be used to prove that for $$X, Y, Z \in \mathbb{F}_{\large p^{\Large n}}$$, $$Z = X \cdot Y$$ have been multiplied correctly; and how exactly would you do it? How would you keep track of the reduction modulo $$\alpha^{\large n}+1$$, such that when you multiply $$X(s)$$ by $$Y(s)$$, that still somehow corresponds to $$Z(s)$$. In the paper they defined their hash function to be $$f_{\large \mathbf{a}}(\mathbf{x}) = \sum_{\large i=1}^{\large m} \mathbf{a}_{\large i} \cdot \mathbf{x}_{\large i}$$ where each $$\mathbf{a}_{\large i}$$ and $$\mathbf{x}_{\large i}$$ are elements of $$\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$$, such that every $$\mathbf{x}_{\large i}$$ has binary coefficients. So I am also wondering if (assuming this is even doable, at all) this probabilistic proof can be extended to linear combinations of such products? So that I could, given some computed "$$f_{\large \mathbf{a}}(\mathbf{x})$$", check (probabilistically) if it is actually $$f_{\large \mathbf{a}}(\mathbf{x})$$, or a fake. And would the probability of correctness - per point comparison - change too?

# EDIT: Just for closure

Although you cannot directly apply this lemma to the "polynomials" that I talked about, it can still be adapted to work, as seen in this paper. The main idea is that, when analysing polynomial multiplication in a quotient ring, you get some kind of circulant matrix (as mentioned by Mark Schultz-Wu) as the representation of the transformation that happens, which you can leverage to your advantage to compute point evaluations quicker - and then just do a bunch of point evaluations in a specific way to produce probabilistic proof

Infact, you can build entire proof systems over these kinds of quotient rings.

• Consider what it means to "evaluate" a polynomial $X \in \mathbb F_{p^n}$ at $s \in \mathbb F_p$. This will not produce enough data to fully characterize $X$ or its products. In the case $p=2$ we would evaluate a polynomial only at $s=0,1$. That's not enough information to recover $X$ or any of its products with other "polynomials" in $\mathbb F_{p^n}$. Mar 28 at 17:18
• I know that in the case of normal polynomials (i.e. not modulo some other polynomial), a polynomial of degree $n-1$ can be fully characterised by $n$ points $(p_0, X(p_0)), \dots, (p_{n}, X(p_{n}))$. How many such "points" do you need to characterise a "polynomial" in $\mathbb{F}_{\large p^{\Large n}}$? Is it significantly more? Mar 28 at 17:31
• Sorry I misspoke, I didn't mean to say polynomial in $\mathbb{F}_{\large p^{\Large n}}$. I meant to ask instead, how many points you need to characterise a polynomial in the quotient ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$. So it's coefficients are in the finite field $\mathbb{Z}_{\large p}$. I'm guessing that means the number of points needed becomes $p^n$? Or does the "quotient ring" aspect make the points needed $(p^n)^n$ - as you said? Mar 28 at 17:51
• Assuming $\alpha^n + 1$ is irreducible over $\mathbb F_p$, then the quotient ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$ is a field of characteristic $p$ with $p^n$ elements. So limiting ourselves to polynomials of degree less than $n$, we have unique representatives for those $p^n$ elements as polynomials in $\alpha$. Evaluating these at arguments $s \in \mathbb F_p$ gives only $p$ possible results. In short two such polynomials can be different but agree on all those $p$ results. Mar 28 at 18:25
• I see, so there just isn't enough information. Thanks. Mar 28 at 18:33

And in the paper they use $$n=2^k$$ and $$q−1=2n$$, which makes $$\alpha^n+1$$ the cyclotomic polynomial $$\Phi_{2n}(\alpha)$$ (which makes polynomial multiplication more efficient because Chinese remainder theorem? I'm not too sure),

namely I'll explain the last part briefly. This is a typical optimization in lattice-based cryptography, using FFT-type techniques known as the "Number Theoretic Transform".

The big idea is to mimic the FFT. This defines an isomorphism $$(\mathbb{C}^n, +, \ast)\cong (\mathbb{C}^n, +, \circ)$$. Here, both sides are rings, e.g. you can add, subtract, and multiply. The addition/subtraction is how you expect (coordinate-wise). Multiplication is

• $$\ast$$: (cyclic) convolution, e.g. $$(\vec a\ast\vec b)_i = \sum_{j+h = i}\vec a_j\cdot \vec b_h$$, where $$\cdot$$ is the standard multiplication over $$\mathbb{C}$$, and
• $$\circ$$: Hadamard (coordinate-wise) multiplication, e.g. $$(\vec a\circ \vec b)_i = \vec a_i\cdot \vec b_i$$.

In other words, given $$\vec a, \vec b\in (\mathbb{C}, +, \ast)$$, one can compute $$\vec a\ast \vec b$$ either naively ($$O(n^2)$$ $$\mathbb{C}$$-ops), or more intelligently. A particularly intelligent thing to do is

1. compute $$\hat{a} = \mathcal{F}(\vec a), \hat{b} = \mathcal{F}(\vec b)$$ using the FFT in $$O(n\log n)$$ ops,
2. compute $$\hat{c} = \hat{a}\circ\hat{b}$$ in $$O(n)$$ ops, then
3. compute $$\vec c = \mathcal{F}^{-1}(\hat{c})$$ in $$O(n\log n)$$ ops.

So in total one gets $$O(n\log n)$$ multiplication, compared to the naive $$O(n^2)$$ multiplication.

As I said, the idea is to mimic the FFT. Instead, we now have the isomorphism

$$(\mathbb{Z}_p[\alpha]/(\alpha^{n}+1), +, \ast)\cong (\mathbb{Z}_p^n, +, \circ)$$

Where $$\ast$$ is polynomial multiplication in $$\mathbb{Z}_p[\alpha]/(\alpha^n+1)$$ now. This corresponds to something related to circular convolution, but not exactly circular convolution (it is now "negacyclic"). Essentially, polynomial multiplication in $$\mathbb{Z}_p[\alpha]/(\alpha^{2n}-1)$$ corresponds to circular convolution. This ring may be written as $$\mathbb{Z}_p[\alpha]/(\alpha^{2n}-1)\cong \mathbb{Z}_p[\alpha]/(\alpha^n-1)\times\mathbb{Z}_p[\alpha]/(\alpha^n+1)$$. We work in the "right" sub-ring here, as the left sub-ring splits further (because $$\alpha^n-1$$ is a reducible polynomial. In particular, one may write it as a suitable product of cyclotomic polynomials).

Anyway, to mimic the FFT, we need the isomorphism

$$(\mathbb{Z}_p[\alpha]/(\alpha^{n}+1), +, \ast)\cong (\mathbb{Z}_p^n, +, \circ)$$

to actually hold. In particular, we need $$\mathbb{Z}_p[\alpha]/(\alpha^n+1)$$ to be "suitably like $$\mathbb{C}$$", namely it needs to have a "good enough" root of unity. In particular, it needs to have a $$2n$$th root of unity. A necessary and sufficient condition for this is that $$p-1\equiv 2n$$. This is because $$\mathbb{Z}_p$$ is a field ($$p$$ is prime), so the group of invertible elements $$\mathbb{Z}_p^\times$$ has order $$p-1$$, and is particular cyclic. A "good enough" root of unity $$i$$ would satisfy $$i^n\equiv -1\bmod p$$, or equivalently $$i^{2n}\equiv 1\bmod p$$. This leads us to the condition $$p-1\equiv 2n\bmod p$$.

As for connections to the CRT, this is true, but only because the CRT (over polynomial rings) is secretly the source of the FFT as well. If you're interested about it for lattices, the relevant application of the CRT is something like (I haven't checked)

$$\mathbb{Z}_p[\alpha]/(\alpha^n+1)\cong \prod_{i} \mathbb{Z}_p[\alpha]/(\alpha-\zeta^i)$$

coming from the factorization modulo $$p$$ $$(\alpha^n+1)\bmod p \equiv \prod_i (x-\zeta^i)\bmod p$$. You can then apply the CRT to write the polynomial ring as the product of 1D rings. Note that projecting a polynomial $$p(x)$$ to each of these 1D rings is precisely equivalent to evaluating the polynomial at some power of $$\zeta^i$$. Efficiently evaluating this isomorphism at all the points $$\zeta^i$$ still requires some tricks (this is the content of the FFT --- naively it is still $$O(n^2)$$ complexity), but can be done.

But then I am thinking, since any element $$X \in \mathbb{F}_{\large p^{\Large n}}$$ can be thought of as a polynomial, can you "evaluate" that polynomial at some point $$s \in \mathbb{F}_{\large p}$$? I mean obviously you can in the sense that you can just compute $$X(s)$$: $$\mathbb{Z}_{\large p} \ni X(s) = {\sum_{\large k=0}^{\large n-1} x_{\large k} \cdot s^{\large k}} \mod p$$ but my question is whether doing so is "correct"? Or is this just nonsense gibberish that doesn't map onto anything. The reason I wanna know is because this lemma allows for proving (probabilistically) that a polynomial multiplication $$C = A \cdot B$$ was performed correctly, by picking some random $$p$$ and checking if $$C(p) = A(p) \cdot B(p)$$, over and over again.

That does not apply to the case you're thinking of. While for polynomials, you can check if $$C(p) = A(p) \cdot B(p)$$, however when you're multiplying field elements (expressed as polynomials), you are not doing simple polynomial multiplication. Instead, you are doing polynomial multiplication modulo a third polynomial and that messes things up.

To take the simplest possible case, consider $$GF(2^2)$$. That has four elements, $$0$$, $$1$$, $$x$$ and $$x+1$$ (if we use a polynomial representation), and multiplication is done via the irreducible polynomial $$x^2 + x + 1$$ (which happens to be the only irreducible polynomial of degree 2 for $$GF(2)$$).

Now, in $$GF(2^2)$$, we have $$x \cdot (x+1) = x^2 + x \bmod x^2 + x + 1 = 1$$.

However, if we were to run your test by setting the polynomial input $$x = 0$$, the left hand side would be $$0 \cdot (0+1) = 0$$, while the right hand size is 1. Hence, your test concludes that the multiplication result is not correct, when in fact it is.