## Friday, November 03, 2017

### Full iterative modular inverse example

Figured out my own way to calculate the modular inverse which is then the third fundamental way now known. Here will give a full iterative example showing how can tackle any modular inverse calculation.

Post walks through finding the modular inverse of 101 modulo 1517, which is 751, with my discovery. Talk a lot at beginning as talk through setting things up.

To get something that will need to iterate probably need to go larger than have done in prior examples, so will use  N= 37(41) = 1517. Like using composites as presumably should be a little harder but doesn't really matter, I don't think, with my method. Let's use r = 101. And will use m = 47. There are several variables where you get to choose. With m, I like to choose such that its square is greater than the modulus. May not be necessary but with early research will just go with what I like.

Have given the system LOTS and is in this post but at end, as I want to just dive into the method, up here. Will let y0 = 1 as usual, just is easy. Further research may indicate should give it some other value.

Then: F0 = 101(101+2(47)) = 101(195) = 19695 = 1491 mod 1517

Tempted to use the smaller negative, but will continue with it. Next equation:

2(47)(1491)d = [1491(n-1) - 1](101 + 2(47)) = 998n - 193 mod 1517

590d = 998n - 1193 mod 1517

Here both coefficients are even, so will use 1517-1193 = 324.

590d = 998n + 324 mod 1517, and can now divide off shared factors.

295d = 499n + 162 mod 1517

Will go with smaller modulus, so want 295 to divide across.

So: 499n + 162 = 0 mod 295

Which is: 204n + 162 = 0 mod 295, so: 204n = -162 mod 295

And can divide off some factors: 102n = -81 mod 295, so: 34n = -27 mod 295

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

Whew! So can recurse! Need modular inverse of 34 modulo 295. r' = 34, N' = 295.

Should note how much smaller the modulus is with next iteration. There will be a smaller modulus to recurse with next guaranteed as of course each coefficient will be smaller than N.

Will let m' = 23, where again is arbitrary choice but do like picking primes, and y'0 = 1 as usual, which is also arbitrary. May turn out should pick some kind of way and have some other value for optimization. Am just demonstrating here though, so is ok.

F'0 = 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

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

While as a solution to divide off coefficient still also have n' = 1 mod 295. Is maybe kind of notable how that works? Am looking for a solution modulo 295, so the 40 will divide off. And n'=1 will work, so while found modulo 59, is also value modulo 295.

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

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 also d' = 116 mod 295. Ok, on to next thing then.

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

So now with: 34n = -27 mod 295

Now can get: n = -27(269) = -278 = 112 mod 295.

Which is our solution for an equation modulo 1517, so have n = 112 mod 1517

So yeah, again how that works is found a value to allow a coefficient to divide across, so is valid modulo our N.

And from before:

295d = 499n + 162 mod 1517

And now

295d = 499(112) + 162 = 56050 mod 1517, so d = 190 mod 1517

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

r-1 = (112-1)(101 + 2(47)) - 2(47)(190) =  111(195) - 1173 = 751 mod 1517

And 101(751) = 1 mod 1517 as required.

And some thoughts. Actually is better when nothing divides off the modulus. Doesn't seem to even want to let you cheat some kind of way. The math behaves as if, yeah there were shared factors to divide off. Then you MAY have to increment like I did, so maybe is good that popped up in this example.

Whew! Definitely something to let a computer do. But will admit for me is interesting to work through in detail.

So is demonstrated how you can iterate with the system, and then walk back to the final answer.

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

r-1 = (n-1)(r + 2my0) - 2md mod N

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

2mdF0 = [F0(n-1) - 1](r + 2my0) mod N

and

F0 = r(r+2my0) mod N

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

Copied from my post: Modular Inverse Innovation

It is also derived there.