Translate

Tuesday, May 09, 2017

Modular inverse innovation

Figured out a way to calculate the modular inverse of some residue r modulo some integer N, by leveraging a modular factorization. Will give the working system, show an example then give the derivation.

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

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

Example: Calculate the modular inverse of 11 modulo 137.

With N = 137, I will use m = 12, as: 7 = 144 mod 137

And looking at simple will use y0 = 1, so:

F0 = 11(11+2(12)(1)) = 11(35) = 111 mod 137

61d = 49n - 84 = 7(7n - 12) mod 137

If we now let d = 7d', get to 61d' = 7n - 12 mod 137, and n = -7 works with d' = -1.

So d = - 7, with n = -7, giving r-1 = (-7-1)(11+2(12)(1)) - 2(12)(-7) mod 137

So:  r-1 = -6 + 31 = 25 mod 137, and 11(25) = 1 mod 137 as required.

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

Derivation:

Given, some residue r modulo N whose modular inverse is to be determined, find D such that: m2 = D mod N, and m does not equal r.

Then for some  x2 - Dy2 = F, I have the modular factorization modulo N:

(x-my)(x+my) = x2 - Dy2 = F mod N, and can set:

x - my = r mod N, then x+my =Fr-1 mod N.

Solving for x, with x = my + r mod N, and substituting into x2 - Dy2 = F gets me:

r(r+2my) = F mod N

So I can look at a y0 which will give an F0, and a difference of d, such that:

y = y0 + d

And subtract that F from a multiple n, of my initial F, substituting for y:

nF0 - F = r[(n-1)(r+2my0) - 2md] mod N

Now consider, nF0 - F = 1 mod N, which gives:

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

And can solve from there for the modular inverse:

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

Now can substitute into x+my =Fr-1 mod N, using x = my + r mod N, and simplify somewhat to get the control equation:

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

and from before I have to show the full system as given:

F0 = r(r+2my0) mod N

Derivation complete.


James Harris
-------------------------------

Want a PDF? You can get one at my math group. There is a post there with a PDF attached.

Friday, May 05, 2017

Chasing the modular inverse

For years I've talked about the easy modular factorization with x2 - Dy2 = F.

Which is, when m2 = D mod C, where C is some integer:

(x-my)(x+my) = x2 - Dy2 = F mod C

And then I'd use some residue r.

Where one way is: x - my = r mod C, then x+my = Fr-1 mod C

Where for years have wondered about that modular inverse, and found myself pondering, can you use these equations to figure it out? So why now? I don't know. Just playing around.

Next thing I knew was looking at C = 111 = 3(37) where picked for easy. And noticed that a close square is 121, so got m = 11, and D = 10.

Then went for a prime for r, kind out of habit, and need one coprime to 111, wasn't going to use 2, so went with r = 5.

So had: x - 11(1) = 5 mod 111, so x = 16 mod 111

Then I calculated F, from x2 - 10y2 = F, and got F = 24 mod 111.

So had 16 + 11(1) = 24r-1 mod 111, so 27 = 24r-1 mod 111

Which didn't seem to get me anywhere. But I noted means: 5(27) = 24 mod 111

So I'm like, ok, why not use y = 2? And after same process got: 5(49) = 23 mod 111

And, I realized could subtract one from the other to get 5(27 - 49) = 5(-22) mod 111, so:

5(89) = 1 mod 111

So I got the modular inverse, but was that luck? And now finally decided to go more formal, so here is the full system:

 x2 - Dy2 = F, m2 = D mod C, where C is some integer.

(x-my)(x+my) = x2 - Dy2 = F mod C,  x - my = r mod C, then x+my =Fr-1 mod C

Solving for x, with x = my + r mod C, and substituting into x2 - Dy2 = F gets me:

r(r+2my) = F mod C

So I can look at a y0 which will give an F0, and a difference of d, such that:

y = y0 + d

And played around enough to know I needed a variable n, where will just give what I got without explaining everything in detail. Is easy math though, so not hard to retrace.

nF0 - F = r[(n-1)(r+2my0) - 2md] mod C

And chasing after modular inverse, nF0 - F = 1 mod C, would be nice, so have:

r[(n-1)(r+2my0) - 2md] = 1 mod C

And then:

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

Finally now then I have control equations with:

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

and

F0 = r(r+2my0) mod C

So now I don't even see the original x2 - Dy2 = F or the other equations. Just see those three, but originals must be valid for it all to work! Must keep that in mind. First was thinking oh, they just went away. Nope. Math knows they are there.

Well now can see how n = 1, and d = 1 worked, with r = 5 mod 111.

So was just luck, huh? So you CAN just say, pick n, but then have potential of needing a modular inverse to calculate d, or vice versa. Oh yeah, m cannot equal r for this approach to work! Should note that as well.

Also may as well check my new equation since know n =1, works, and clips off the front too.

And: r-1 = -2(11) = 89 mod 111, as we got above.

Went ahead and tried r = 41 mod 111, just to use something bigger, so again m = 11 and y0 = 1. And got:

105d = 3n - 66 mod 111, where d = 1 will work with: n = 57

And that gives r-1 = 65 mod 111, which works: 41(65) = 1 mod 111

And just playing around. So yes, can calculate a modular inverse this way, potentially. Definitely can get to another modular inverse to solve for n or d, but may not be necessary if can just figure them out like with my simple experiments. But who knows how often is that easy? I don't.

Wonder if could be proven.... Possibly something for some other time. These simple experiments have been rewarding and extremely interesting.

Glad did some experiments and some derivation.

Can be SO much fun to play with the math.


James Harris