I'm trying to understand a Montgomery reduction algorithm, for which I need to calculate a multiplicative inverse. However, euclidean algorithm only helps if A < B.

Example is 11 mod 3. Multiplicative inverse of 11 is 2,but ext_gcd gives you Bezout numbers such as -1 and 4.

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Wikipedia says so: The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a.

But as far as I see this can't be true, either X is multiplicative inverse of A modulo B or Y is multiplicative inverse of B modulo A, but not both at the same time, because one of them (A or B) is going to be bigger than another. We have X=4, Y=-1 for A=3,B=11, and X=4 is valid inverse, while -1 is indeed not.

A lot of online calculators that I tried are also said that a has to be bigger than be, but they (some of them) are still able to calculate inverse of 11 mod 3.

The only workaround I found so far is perform A = A mod B first, so A is now a remainder of divisios and therefore is less than modulus, so we can perform ext_gcd(2, 3) now and get our 2 as answer.

Probably I'm missing something, this thing is pretty new for me.

Thanks.

  • "We have X=4, Y=-1 for A=3,B=11, and X=4 is valid inverse, while -1 is indeed not. " Huh. $X \equiv A^{-1}\mod B$ because $X*A = 4*3 \equiv 1 \mod 11$. An $Y\equiv B^{-1} \mod A$ because $Y*B=(-1)*11 \equiv 1 \mod 3$. They are both valid inverses. What is your issue? – fleablood Jun 15 at 18:48
  • $-1\equiv 2 \mod 3$. So $-1$ is equivalent to $2$. It doesn't make the slightest difference which one you use. (We don't call these things "equivalences" for nothing, you know...) – fleablood Jun 15 at 19:16
  • "A lot of online calculators that I tried are also said that a has to be bigger than be," Calculators don't do mathematics. Calculators do calculations. – fleablood Jun 15 at 19:24
up vote 0 down vote accepted

It is inevitable that a Bézout's identity equation will give you modular multiplicative inverses, since given:

$$am+bn = 1$$

we can take $\bmod m$ for

$$ bn\equiv 1 \bmod m$$

or $\bmod n $ for

$$ am \equiv 1 \bmod n$$

To get $a$ and $b$ in your preferred range, you can simply add or subtract a suitable multiple of the modulus.

So in this case $$-1\cdot 11 + 4\cdot 3 = 1$$

and thus $$-1\cdot 11\equiv 1 \bmod 3$$

($-11$ being one more than $-12$), so $-1$ is a valid inverse of $11$ modulo $3$. Then of course $$-1\equiv 2 \bmod 3$$

so this is consistent with your observation that $2$ is the inverse of $11 \bmod 3$ also.

  • I now understand why this is correct from algorithmical point of view, but I don't understand why −1 ≡ 2 mod 3. I miss some math-related thing. – Danetta Jun 18 at 9:12
  • Presumably you have no problem with $11 \equiv 8\equiv 5 \equiv 2 \bmod 3$. In each case, add one and you arrive at a multiple of $3$. The same applies to $-1$. Also, the difference between $-1$ and $2$ is a multiple of $3$ (as is true for any pair of the equivalent values above). – Joffan Jun 18 at 12:52

$-1 \equiv 2 \mod 3$ so they are considered to be the same thing.

That's we we call these equivalence classes.

However, euclidean algorithm only helps if A < B

I simply do not understand why you say that.

either X is multiplicative inverse of A modulo B or Y is multiplicative inverse of B modulo A, but not both at the same time, because one of them (A or B) is going to be bigger than another. We have X=4, Y=-1 for A=3,B=11, and X=4 is valid inverse, while -1 is indeed not.

Except, of course, it indeed is. $-1*11 = -11 \equiv 1 \mod 3$. That is the valid inverse. Why do you think it is not?

It doesn't matter if $A > B$ or $B> A$ as $\gcd(A,B) = 1$ Euclid's algorithm will give us:

$mA + kB = 1$ so $k \equiv A^{-1} \mod B$ and $m \equiv B^{-1} \mod A$ simultaneously.

Is your concern that one is represented with a positive number and the other negative?

That's irrelevent.

It doesn't matter which representative we use to represent a class. We could have used $50\equiv -1 \mod 3$ so $50 \equiv 11^{-1}\mod 3$ for all we care. (Indeed $50*11 = 550 = 3*183 + 1 \equiv 1\mod 3$).

Note: if $mA + kB = 1$ and $m > 0$ but $-A < k < 0$ then

$mA + (k+A)B = 1 + BA\equiv 1 \mod A,B,AB$ and $m$ and $(k+A)$ are still the proper inverses. ANd $m > 0; k+A > 0$.

Indeed $(m + vB)A + (k + uA)B = 1 + (v+u)AB$ so $m + vB\equiv A^{-1} \mod B$ for any integer $v$ and $k + uA \equiv B^{-1} \mod A$ for any integer $u$.

  • "Is your concern that one is represented with a positive number and the other negative?" — Yes, I haven't even considered negative numbers. I'm still not exactly sure how −11 ≡ 1 mod 3. For me logically it looks like quotient of -11/3 is -3, so remainder is either 2 or -2, but how is it 1? – Danetta Jun 18 at 8:56
  • It looks like a rule to "just take a remainder from division" stops working there. Do I need positive inverse for Montgomery or it doesn't matter? – Danetta Jun 18 at 9:17
  • $-11 = 3*(-4)+ 1$ so $-11 \equiv 1 \mod 3$ and $-11 = 3*(-3) -2$ so $-11 \equiv -2 \mod 3$. And $1 \equiv -2 \mod 3$. As well $-11 = 3*(-7)+12$ so $-11 \equiv 10 \mod 3$. But $-11 \ne 3*k + 2$ for any integer $k$ so $-11 \not\equiv 2 \mod 3$. A remainder means any $p = d*n + r$ and $d$ can be any value positive or a negative and $r$ can be any value that works. But THE remainder would mean $p=d*n+r;0\le r< n$ would mean the remainder is unique, positive and less than the divisor. If $p < 0$ this means $d < 0$ and $r \ge 0$. – fleablood Jun 18 at 15:01
  • I dont know how to do the Montgomery method. It seems as though you must already now then inverse to use it and that it is just an computational efficient method to do multiplication. – fleablood Jun 18 at 15:18

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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