Modulus operator
Arithmetic operations on a finite field F_p
for a prime p
are defined as the operator over natural numbers, modulo p
For eg. addition over the finite field is defined as follows
a ⊕ b = (a + b) % p
To define all relevant arithmetic operations over the fintie field, we need to implement the modulus operator inside circom. We perform modulo in such a way that long division is avoided. The algorithm is as follows -
Implementation
Let the prime p
for the curve be defined as p = 2255 - 19. Given input x
, we need to calculate x % p
We define c = 2^255
.
Now,
r = x % 2^255
Note
Note that
r
< 2255
Also,r
is simply the least significant 255 bits ofx
q = x // 2^255
Note
q
is simplyx
sans the least significant 255 bits ofx
Hence we derive equation (1)
x = q*c + r
x = q*(p+19) + r -- (1)
Simplifying (1) and taking modulus p
on both sides
x % p = 19*q % p + r % p
Now, calculate r % p
as:
if (r>=p): r % p = r - p
if (r<p): r % p = r
Apply this algorithm recursively to calculate 19q % p
. In the circuit, we apply the above algorithm recursively, and hence x
can be of arbitrary size.
Note
Calculating
r % p
, there is not way to define conditional logic inside a circuit. However, a multiplexer serves the same purpose when one out of multiple values needs to be selected. In this particular case, we provide bothr
andr-p
as the input signals to the multiplexer, and assign the selector to be0 | 1
based on whetherr - p
underflowed or not.