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.$$
a = q-a
should bea = a-q
, I guess. Also, even with this fix, only the range[1..2*q-1]
is handled correctly. A more generic modular reduction of non-negativea
moduloq
uses a loop to subtractq
as much as needed:while ( a >= q ) { a = a-q; }
. $\endgroup$ – fgrieu♦ Jan 15 '19 at 11:46