# El Gamal Signatures, Need help explanining a step, Where does the “775” come from? Image included

I understand all of the previous steps, but I don't understand what is happening to "S2" in that the number "775" showed up.

Where does the 775 come from? I can't seem to get it, and I've tried modding it, but received the wrong answer.

The answer to this is to add the modulo to the a when a is negative. As such, this worked out fine after I added the modulo to the negative number.

Solved!

• $(300 - 61\cdot 425) \equiv 775\ \pmod{880}$ – Maeher Dec 10 '18 at 8:01
• To see it, just look at both side of $(300−61⋅425)* 553 ≡775 * 533$. – kelalaka Dec 10 '18 at 8:02
• Thanks, but that's not the answer I get on my calculator. Should I solve within the parentheses first and follow order of operations, then mod by 880? – J. Doe Hue Dec 10 '18 at 8:04
• I see how you got the answer now. However, I get a negative, and my calculator doesn't process negative numbers for the MOD operation. How else can I solve this problem using the negative in the parenthesis? – J. Doe Hue Dec 10 '18 at 8:09
• When you get negative add the modulus. – kelalaka Dec 10 '18 at 8:19

The question basically is how $$300 - 61 \cdot 425 \bmod 880$$ can turn into the value $$775$$, while a calculator returns a different value, likely $$-105$$. The difference is that sometimes a remainder is taken to have a value in the range $$(-N, N)$$ rather than $$[0, N)$$.
$$300 - 61 \cdot 425 = -25625$$. So you can say that we're trying to find a value $$x \cdot 880 + y = -25625$$. Now is can be $$-29 \cdot 880 - 105 = -25625$$ to find a value within $$(-N, N)$$, similar to finding $$29 \cdot 880 + 105 = 25625$$. $$-105$$ is then commonly called "the remainder"; it's what you would get if you would perform simple tail division yourself.
However, for cryptographic operations we generally try and perform operations in a group of order $$N$$ instead, with $$N$$ possible values in the range $$[0, N)$$. so in that case we can take $$-30 \cdot 880 + 775 = -25625$$, and the result will be $$775$$, exactly $$880$$ more than $$-105$$ in other words. This is commonly called taking the modulus, although this value can also be called a remainder.
So to find the right value within your calculator you can simply add $$N = 880$$ if the result is negative. A little trick in programming languages is to perform ((X % N) + N) % N, so that an if statement can be avoided. Note though that the + N may cause an overflow for large values of $$N$$.