**System:**

**r**

^{-1}= (n-1)(r + 2my_{0}) - 2md mod NWhere y

_{0}is chosen as is m, with m not equal to r, and n and d are to be determined. They are found from:

**2mdF**

_{0}= [F_{0}(n-1) - 1](r + 2my_{0}) mod Nand

**F**

_{0}= r(r+2my_{0}) 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

_{0}= 1, so:

F

_{0}= 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

^{2}= D mod N, and m does not equal r.

Then for some x

^{2}- Dy

^{2}= F, I have the modular factorization modulo N:

(x-my)(x+my) = x

^{2}- Dy

^{2}= 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

^{2}- Dy

^{2}= F gets me:

r(r+2my) = F mod N

So I can look at a y

_{0}which will give an F

_{0}, and a difference of d, such that:

y = y

_{0}+ d

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

nF

_{0}- F = r[(n-1)(r+2my

_{0}) - 2md] mod N

Now consider, nF

_{0}- F = 1 mod N, which gives:

r[(n-1)(r+2my

_{0}) - 2md] = 1 mod N

And can solve from there for the modular inverse:

**r**

^{-1}= (n-1)(r + 2my_{0}) - 2md mod NNow can substitute into x+my =Fr

^{-1}mod N, using x = my + r mod N, and simplify somewhat to get the control equation:

**2mdF**

_{0}= [F_{0}(n-1) - 1](r + 2my_{0}) mod Nand from before I have to show the full system as given:

**F**

_{0}= r(r+2my_{0}) 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.

## No comments:

Post a Comment