Finding modular inverse simplified

Back in 2017 found a new way to calculate the modular inverse giving world a third one along with method by Euler and extended Euclidean algorithm.

Will give a simplified version which I use. So is my usual approach where can adjust of course if notice an area can improve.

And I just use equals rather than congruence symbol.

To get modular inverse of r modulo N, first pick k for F₀ = rk mod N such that rk is greater than N such that F₀ and N do not share prime factors.

Then have unknowns d and n where:

F₀ d = [F₀ n - (F₀ + 1)]k mod N

You solve for d often by recursion, so can divide off F₀ as can now get:

0 = (F₀ kn) mod N - [(F₀ + 1)k] mod N mod F₀ 

If F₀ k though is less than N subtract N which is required to prevent F₀ from still being a factor. Which means can have a new modular inverse to find but now where F₀ is modulus, so shrank.

Recurse until have an inverse and then roll up to get n. Usually takes me one or two recursions but like studying small primes.

When have solved for n, you get modular inverse of r from:

r^-1 = (n-1)k - d mod N

Now will do an example to demonstrate.

With N = 137, will find modular inverse of 53. 

Already have done from some research was doing so can just copy over. Picking k = 3 as is smallest multiple that gets 53 greater than 137.

F₀ = 53(3) = 22 mod 137

22d = (22n - 23)(3) = 66n - 69 mod 137

So need to subtract to get:

22d = -71n - 69 mod 137, so: 0 = -5n - 3 mod 22

5n = -3 = 19 mod 22 and can recurse now to find modular inverse of 5.  Picking k' = 5 and 5(5) = 3 mod 22.

So: 3d' = (3n' - 4)(5) mod 22, so: 3d' = 15n' - 20 mod 22

And subtract 22 to get: 3d' = -7n' - 20 mod 22

So: 0 = -n' - 2 = 0 mod 3, giving n' = 1.

Then: 3d' = -7(1) - 20 = -27; d'= -9

So: 5^-1 = (1-1)(5) - (-9) = 9 mod 22

So now I just use to get:

n = 9(19) mod 22, so n = 17

So: 22d = -71(17) - 69 = -1276

Where now can divide off 22, and you have: d = -58 mod 137

Then 53^-1 = (17-1)(3) - (-58) = 106 mod 137

And yup, 53(106) = 1 mod 137.

That is my simplified approach. Can also use full system where get a few more symbols. I give that and derivation in post: Modular inverse innovation