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

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

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 y₀ = 1, so:

F₀ = 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: m² = D mod N, and m does not equal r.

Then for some  x² - Dy² = F, I have the modular factorization modulo N:

(x-my)(x+my) = x² - Dy² = 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 x² - Dy² = F gets me:

r(r+2my) = F mod N

So I can look at a y₀ which will give an F₀, and a difference of d, such that:

y = y₀ + d

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

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

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

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

And can solve from there for the modular inverse:

 r^-1 = (n-1)(r + 2my₀) - 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:

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

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

F₀ = r(r+2my₀) 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.