What is the difference between subtracting the modulus from a scalar field element and reducing it?

Question

When implementing a Field element, we define the necessary operations on the data structure.

One function that I see is a "scalar reduce" function, which effectively reduces a random scalar so that it is in the scalar field.

What is the difference between this and subtracting the modulus from such number?

Example:

Let a be a scalar chosen at random Let q be the modulus

I have seen code that does the following:

if a > q{
  a = q-a
}

Why did it not try to reduce a by doing the modulus?

Answer 1

We have many mathematical operations for the Cryptography as $$\neg, \ll, \gg , \oplus, + , \times, /, \operatorname{mod}, \operatorname{div}, \operatorname{exponential},\ldots$$ and the list goes on. As we all knew that the time is money and all of the operations have some cost. Our aim is the minimize the cost as much as possible.

For example, we prefer left shifts to multiplication by powers of two

$$ n \cdot 2^k = n \ll k$$

or right shifts to division by the powers of two

$$ n / 2^k = n \gg k$$

or combination of bitwise and operator ($\wedge$) and subtraction by 1 to remainder by the powers of two

$$ n \mod 2^k = n \wedge (2^k-1).$$

The cost of multiplication and division is reduced into the cost of the shift operation and the cost of the remainder into $\wedge$ (modulus $2^k$ is equivalent to taking the $k$ least significant bits).

---

In your question, you wrote

if a > q{
  a = q-a
}

This should be

if a >= q{
  a = a-q
}

for modular reduction by subtraction as noted by @fgrieu's in the comments.

In your case, we have a prime number $q$ and we are trying to take the modulus. One way during the calculations is to reduce modulo at the end. However, this may increase the size of the operands and this will result in larger operation costs.

What I can see from your piece of code that they reduce the number by subtraction with $q$. Assuming that the result $r = a-q$ is always in $$0 \leq r < q$$ then we can say that $$q\leq a<2q,$$ to see this subtract $q$ from the above equation;

$$q-q \leq a-q <2q-q$$ and get

$$0 \leq a-q=r <q.$$