The Pasta curves that we use in halo2 are designed to be highly 2-adic, meaning that a large multiplicative subgroup exists in each field. That is, we can write with odd. For both Pallas and Vesta, ; 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 modulo one of the Pasta primes , where is a non-zero square in . We define a root of unity where is a non-square in , and precompute the following tables:

Let . We can then define as an element of the multiplicative subgroup.


i = 0, 1

Using , we lookup such that


i = 2

Lookup s.t.


i = 3

Lookup s.t.


Final result

Lookup such that

Let .

We can now write

Squaring the RHS, we observe that Therefore, the square root of is ; the first part we computed earlier, and the second part can be computed with three multiplications using lookups in .