Skip to content
LogoLogo

Multiplying in the Exponent

From repeated exponentiation to multiplication

Here, we explain a fairly simple mathematical idea that underpins our multiplication technique. We fix a number nmuln_\text{mul} of MUL constraints; we recall the constraint arrays pp, qq, lo\text{lo} and hi\text{hi}. Each of these arrays is of length nmuln_\text{mul} and contains 64-bit words.

For each x∈{0,…,nmul−1}x \in \{0, \ldots , n_\text{mul} - 1\}, p[x]p[x] and q[x]q[x] are in {0,…,264−1}\{0, \ldots , 2^{64} - 1\}. We're interested in p[x]⋅q[x]p[x] \cdot q[x]. Recall that we work throughout with binary fields. This means that we can't use typical prime-field ideas (like breaking our numbers into limbs so small that their products don't overflow the characteristic, using range checks, and so on).

The Exponentiation Identity

The idea is to use the basic identity (gp[x])q[x]=gp[x]⋅q[x](g^{p[x]})^{q[x]} = g^{p[x] \cdot q[x]}. This is true in all rings, but we have to be careful about reduction in the exponent.

We recall that the multiplicative group of units F2128∗\mathbb{F}_{2^{128}}^* is cyclic; we fix a generator g∈F2128∗g \in \mathbb{F}_{2^{128}}^*. Thus, the multiplicative order of gg in F2128\mathbb{F}_{2^{128}} is 2128−12^{128} - 1.

For each x∈{0,…,nmul−1}x \in \{0, \ldots , n_\text{mul} - 1\}, the array elements p[x]p[x], q[x]q[x], lo[x]\text{lo}[x] and hi[x]\text{hi}[x] are all elements of {0,…,264−1}\{0, \ldots , 2^{64} - 1\}. Our goal is to check whether

p[x]⋅q[x]=?264⋅hi[x]+lo[x]\begin{equation*}p[x] \cdot q[x] \stackrel{?}= 2^{64} \cdot \text{hi}[x] + \text{lo}[x]\end{equation*}

holds as integers. By the basic properties of rings, we know that

gr=gs\begin{equation*}g^r = g^s\end{equation*}

holds if and only if r≡s(modord(g))r \equiv s \pmod{\text{ord}(g)}; in our case, we conclude that

(gp[x])q[x]=gp[x]⋅q[x]=?g264⋅hi[x]+lo[x]=(g264)hi[x]⋅glo[x]\begin{equation*}\big( g^{p[x]} \big)^{q[x]} = g^{p[x] \cdot q[x]} \stackrel{?}= g^{2^{64} \cdot \text{hi}[x] + \text{lo}[x]} = \big( g^{2^{64}} \big)^{\text{hi}[x]} \cdot g^{\text{lo}[x]}\end{equation*}

holds in in F2128\mathbb{F}_{2^{128}} if and only if

p[x]⋅q[x]≡264⋅hi[x]+lo[x](mod2128−1).\begin{equation*}p[x] \cdot q[x] \equiv 2^{64} \cdot \text{hi}[x] + \text{lo}[x] \pmod{2^{128} - 1}.\end{equation*}

Controlling Wraparound

If p[x]⋅q[x]=?264⋅hi[x]+lo[x]p[x] \cdot q[x] \stackrel{?}= 2^{64} \cdot \text{hi}[x] + \text{lo}[x] holds as integers, then it definitely also holds modulo 2128−12^{128} - 1. The converse is not quite true, as we now explain. Since

p[x]⋅q[x]≤(264−1)2=2128−2⋅264+1<2128−1,\begin{equation*}p[x] \cdot q[x] \leq (2^{64} - 1)^2 = 2^{128} - 2 \cdot 2^{64} + 1 < 2^{128} - 1,\end{equation*}

p[x]⋅q[x]p[x] \cdot q[x] can't wrap around modulo 2128−12^{128} - 1. On the other hand, since

264⋅hi[x]+lo[x]≤264⋅(264−1)+264−1=2128−1,\begin{equation*}2^{64} \cdot \text{hi}[x] + \text{lo}[x] \leq 2^{64} \cdot (2^{64} - 1) + 2^{64} - 1 = 2^{128} - 1,\end{equation*}

264⋅hi[x]+lo[x]2^{64} \cdot \text{hi}[x] + \text{lo}[x] can wrap around only in the case of a direct equality 264⋅hi[x]+lo[x]=2128−12^{64} \cdot \text{hi}[x] + \text{lo}[x] = 2^{128} - 1. This equality happens if and only if lo[x]\text{lo}[x] and hi[x]\text{hi}[x] are both 264−12^{64} - 1; and indeed, by choosing at least one of p[x]p[x] and q[x]q[x] to be zero, the prover could get a case in which p[x]⋅q[x]=?264⋅hi[x]+lo[x]p[x] \cdot q[x] \stackrel{?}= 2^{64} \cdot \text{hi}[x] + \text{lo}[x] holds modulo 2128−12^{128} - 1 but not over the integers.

In this latter case, p[x]⋅q[x]p[x] \cdot q[x] is even, while 264⋅hi[x]+lo[x]2^{64} \cdot \text{hi}[x] + \text{lo}[x] is odd. To eliminate it, it thus suffices to ensure to boot that

p[x]⋅q[x]≡264⋅hi[x]+lo[x](mod2).\begin{equation*}p[x] \cdot q[x] \equiv 2^{64} \cdot \text{hi}[x] + \text{lo}[x] \pmod{2}.\end{equation*}

This latter equality is easy to check, since it only depends on the least-significant bits of pp, qq and lo\text{lo}. One simple way to do this is to use AND constraints. It's enough to add 3 new witness words, say p′p', q′q', and lo′\text{lo}', and to constrain that

sll(p′,63)&sll(q′,63)=?sll(lo′,63),\begin{equation*}\mathsf{sll}(p', 63) \mathbin{\&} \mathsf{sll}(q', 63) \stackrel{?}= \mathsf{sll}(\text{lo}', 63),\end{equation*}

as well as that p=p′p = p', q=q′q = q', and lo=lo′\text{lo} = \text{lo}'. The total cost for this is 3 new witness components and 4 new AND constraints (we note that MUL is already much costlier than AND, on a per-constraint basis).

Putting it Together

Assuming that the above issue has been separately resolved, we see that the MUL constraint

p[x]⋅q[x]=?264⋅hi[x]+lo[x]\begin{equation*}p[x] \cdot q[x] \stackrel{?}= 2^{64} \cdot \text{hi}[x] + \text{lo}[x]\end{equation*}

holds over the integers if and only if

(gp[x])q[x]=?(g264)hi[x]⋅glo[x]\begin{equation*}\big(g^{p[x]}\big)^{q[x]} \stackrel{?}= \big( g^{2^{64}} \big)^{\text{hi}[x]} \cdot g^{\text{lo}[x]}\end{equation*}

holds in F2128\mathbb{F}_{2^{128}}. We spend the rest of this site section explaining how to check the exponent condition above.