1
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\begingroup$ If the answer is not satisfactory for you please give the link for the code. $\endgroup$ – kelalaka Jan 15 '19 at 11:05
  • 1
    $\begingroup$ a = q-a should be a = 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-negative a modulo q uses a loop to subtract q as much as needed: while ( a >= q ) { a = a-q; }. $\endgroup$ – fgrieu♦ Jan 15 '19 at 11:46
2
$\begingroup$

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.$$

| improve this answer | |
$\endgroup$
  • $\begingroup$ Got it, so if r < q , then r is in the scalar field q, which is some subgroup for a curve $\endgroup$ – WeCanBeFriends Jan 15 '19 at 13:11
  • 1
    $\begingroup$ Could you read Elliptic Tales. I guess you will like it. $\endgroup$ – kelalaka Jan 15 '19 at 13:16
  • $\begingroup$ Thanks for the recommendation; should be here tomorrow $\endgroup$ – WeCanBeFriends Jan 15 '19 at 13:20
  • $\begingroup$ One question about the inequality: if 0<= r < q. If I were to do the negation of r which I think is -r mod q, then this would also be between 0 and q. Does this mean that there is another point x, s.t. when I negate it, it gives r? $\endgroup$ – WeCanBeFriends Jan 15 '19 at 13:41
  • 1
    $\begingroup$ the $-k$ is represented by $q-k$ in modulus $q$. see this from Math SE $\endgroup$ – kelalaka Jan 15 '19 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.