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.
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.
Using , we lookup such that
Lookup such that
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 .