Common mistake with my modular inverse method

There is one case which can potentially trip people up with my modular inverse method, which is when you have shared factors which divide across the modulus. Will show a case copying and expanding upon and modifying a bit from my full iterative example previously given:

Need modular inverse of 34 modulo 295. r' = 34, N' = 295.

Will let m' = 23, where again is arbitrary choice but do like picking primes, and y'₀ = 1 as usual, which is also arbitrary.

F'₀ = 34(34+2(23)) = 34(80) = 65 mod 295

2(23)(65)d' = [65(n-1) - 1](34 + 2(23)) = [65n' - 66](80) = 185n' - 265 mod 295

40d' = 185n' - 265 mod 295

Dividing off shared: 8d' = 37n' - 53 mod 59, and notice that 37 - 53 = -16, so n' = 1 mod 59 works.

Gives d' = -2 mod 59

If you do NOT divide off across modulus will often get wrong answer. Which happened to me until figured it out, but that is part of the discovery process. Maybe is worth explaining why.

The modular approach is like 40d' = 185n' - 265 + 295j, where j is some unknown integer we don't need to know. But if you divide to get: 8d' = 37n - 53 + 295(j/5), you are assuming j is divisible by 5, which is an error. We don't know what it is and don't want to know.

So correctly is: 8d' = 37n - 53 + 59j, where we assume nothing.

But yuck, now have solution mod 59, and checking took -2 + 2(59) = 116 to work for d'.

So r'^-1 = -2(23)(116) = 269 mod 295. And checking: 34(269)  = 1

Where needed answer modulo 295, and yeah 116 = -2 mod 59.

Is a situation where looks like just have to check various values.

So yeah, when divide off the modulus? Can get a range, and have to try more than one value.

So answer was d' = -2 mod 59, but value needed modulo 295, is d' = 116 mod 295.

That seems to really trip some people up.

------------------------------------------------
Here is the system:

r^-1 = (n-1)(r + 2my₀) - 2md mod N

Where y₀ is chosen as is m, with m not equal to r, and n and d are to be determined. They are found from:

2mdF₀ = [F₀(n-1) - 1](r + 2my₀) mod N

and

F₀ = r(r+2my₀) mod N

---------------------------------------------------

Copied from my post: Modular Inverse Innovation

It is also derived there.


James Harris