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.
Answer
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.
No comments:
Post a Comment