### 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 = 2^{255} - 19. Given input `x`

, we need to calculate `x % p`

We define `c = 2^255`

.

Now,

`r = x % 2^255 `

Note

Note that

`r`

< 2^{255}

Also,`r`

is simply the least significant 255 bits of`x`

`q = x // 2^255`

Note

`q`

is simply`x`

sans the least significant 255 bits of`x`

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 both`r`

and`r-p`

as the input signals to the multiplexer, and assign the selector to be`0 | 1`

based on whether`r - p`

underflowed or not.