Thoughts on my modular inverse derivation and possible algorithm

Thankfully went through a more stepped out derivation of my method for calculating the modular inverse with post: Meta and my modular inverse method

There I finally paid more attention to the requirement from my derivation:

nF₀ = F+1 mod N

Which I noted puts pressure on the math. Which can happen if F₀ shares prime factors with N, as then those have to divide off, for n to exist.

That situation actually occurs in my long example where I didn't realize why then, but simply thought it was an irritation without knowing the why of it happening. And discussed a bit in this post, where now also can talk how to avoid.

Of course F₀ = r(r+2my₀) mod N, so you actually have control there, as you choose m and y₀, which means for an algorithm can actually pick such that F₀ does NOT share prime factors by preventing r+2my₀ = N mod p, for any prime factor p of N. Where of course r has to be coprime already which is a tidbit I've tended to leave out stating as that is obviously required.

Oh yeah, so the derivation is focusing on F = x² - Dy² mod N, as a key equation and finding I can focus on r, and get to F = r(r+2my) mod N, and then self-reference using added variables n and d to get to a solution for the modular inverse:

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

With the control equation:

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

And again my baseline derivation is here.

Importantly my post on the meta aspect also covered how you get to recursion, and emphasized that with next iteration the modulus must be smaller, and can cut at least in half, guaranteed--with each recursion.

Which is really cool.

Now with it figured out, to me is kind of weird how easy it all is.


James Harris