Shorter version of full modular inverse example

Humanity now has a third fundamental way to calculate a modular inverse. Here will step through using my method for calculating the modular inverse showing less than in a previous post where put in a LOT of detail. The calculation is determining the modular inverse of 101 modulo 1517, and the answer is 751. System being used is at end of post.

So: N = 1517, r = 101. Further I choose m = 47, and y₀ = 1

Then: F₀ = 1491 mod 1517

And find:

295d = 499n + 162 mod 1517

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

So: 499n + 162 = 0 mod 295, and find: 34n = -27 mod 295

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

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

Decided to choose m' = 23, and y'₀ = 1

F'₀  = 65 mod 295

And find:

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. And also then have n' = 1 mod 295 as was solving to divide 40 across.

But I have d' = -2 mod 59

And checking took -2 + 2(59) = 116 to work for d'.

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

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

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

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.

Here is the 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

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

Copied from my post: Modular Inverse Innovation

It is also derived there.