Fields

The Pasta curves that we use in halo2 are designed to be highly 2-adic, meaning that a large $2^S$ multiplicative subgroup exists in each field. That is, we can write $p-1\equiv 2^S\cdot T$ with $T$ odd. For both Pallas and Vesta, $S=32$; this helps to simplify the field implementations.

Sarkar square-root algorithm (table-based variant)

We use a technique from Sarkar2020 to compute square roots in halo2. The intuition behind the algorithm is that we can split the task into computing square roots in each multiplicative subgroup.

Suppose we want to find the square root of $u$ modulo one of the Pasta primes $p$, where $u$ is a non-zero square in ${\mathbb{Z}}_p^{\times }$. We define a $2^S$ root of unity $g=z^T$ where $z$ is a non-square in ${\mathbb{Z}}_p^{\times }$, and precompute the following tables:

$$gtab=\left[\begin{array}{cccc}{g}^0& g^1& ...& g^{2^8-1}\\ (g^{2^8}{)}^0& (g^{2^8}{)}^1& ...& (g^{2^8}{)}^{2^8-1}\\ (g^{2^{16}}{)}^0& (g^{2^{16}}{)}^1& ...& (g^{2^{16}}{)}^{2^8-1}\\ (g^{2^{24}}{)}^0& (g^{2^{24}}{)}^1& ...& (g^{2^{24}}{)}^{2^8-1}\end{array}\right]$$

$$invtab=\left[\begin{array}{cccc}(g^{-2^{24}}{)}^0& (g^{-2^{24}}{)}^1& ...& (g^{-2^{24}}{)}^{2^8-1}\end{array}\right]$$

Let $v=u^{(T-1)/2}$. We can then define $x=uv\cdot v=u^T$ as an element of the $2^S$ multiplicative subgroup.

Let $x_3=x,x_2=x_3^{2^8},x_1=x_2^{2^8},x_0=x_1^{2^8}.$

i = 0, 1

Using $invtab$, we lookup $t_0$ such that $$x_0=(g^{-2^{24}}{)}^{t_0}⟹x_0\cdot g^{t_0\cdot 2^{24}}=1.$$

Define ${\alpha }_1=x_1\cdot (g^{2^{16}}{)}^{t_0}.$

i = 2

Lookup $t_1$ s.t. $$\begin{array}{ll}{\alpha }_1=(g^{-2^{24}}{)}^{t_1}& ⟹x_1\cdot (g^{2^{16}}{)}^{t_0}=(g^{-2^{24}}{)}^{t_1}\\ & ⟹x_1\cdot g^{(t_0+2^8\cdot t_1)\cdot 2^{16}}=1.\end{array}$$

Define ${\alpha }_2=x_2\cdot (g^{2^8}{)}^{t_0+2^8\cdot t_1}.$

i = 3

Lookup $t_2$ s.t.

$$\begin{array}{ll}{\alpha }_2=(g^{-2^{24}}{)}^{t_2}& ⟹x_2\cdot (g^{2^8}{)}^{t_0+2^8\cdot t_1}=(g^{-2^{24}}{)}^{t_2}\\ & ⟹x_2\cdot g^{(t_0+2^8\cdot t_1+2^{16}\cdot t_2)\cdot 2^8}=1.\end{array}$$

Define ${\alpha }_3=x_3\cdot g^{t_0+2^8\cdot t_1+2^{16}\cdot t_2}.$

Final result

Lookup $t_3$ such that

$$\begin{array}{ll}{\alpha }_3=(g^{-2^{24}}{)}^{t_3}& ⟹x_3\cdot g^{t_0+2^8\cdot t_1+2^{16}\cdot t_2}=(g^{-2^{24}}{)}^{t_3}\\ & ⟹x_3\cdot g^{t_0+2^8\cdot t_1+2^{16}\cdot t_2+2^{24}\cdot t_3}=1.\end{array}$$

Let $t=t_0+2^8\cdot t_1+2^{16}\cdot t_2+2^{24}\cdot t_3$.

We can now write $$\begin{array}{lclcl}{x}_3\cdot g^t=1& ⟹& x_3& =& g^{-t}\\ & ⟹& u{v}^2& =& g^{-t}\\ & ⟹& uv& =& v^{-1}\cdot g^{-t}\\ & ⟹& uv\cdot g^{t/2}& =& v^{-1}\cdot g^{-t/2}.\end{array}$$

Squaring the RHS, we observe that $(v^{-1}{g}^{-t/2}{)}^2=v^{-2}{g}^{-t}=u.$ Therefore, the square root of $u$ is $uv\cdot g^{t/2}$; the first part we computed earlier, and the second part can be computed with three multiplications using lookups in $gtab$.