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.
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 divisions 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.
$\endgroup$ 32 Answers
$\begingroup$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.
$\endgroup$ 2 $\begingroup$$-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$.
$\endgroup$ 4
