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
Post a Comment