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