Realized that self-reference is key to my way to calculate the modular inverse. And turns out meta just means self-reference, which is easily checked on web with search: define meta
My approach relies on focusing on: x2 - Dy2 = F mod N
When D is a quadratic residue modulo N, you can easily solve for x and y modularly, with D a quadratic residue of N, so there exists m, such that m2 = D mod N.
Then: (x-my)(x+my) = x2 - m2y2 = x2 - Dy2 mod N
So x - my is a residue I like to call r.
And with: r = x - my mod N, then Fr-1 = x + my mod N, and the modular inverse makes its appearance. That is what got me thinking these expressions might be useful to find it.
Can use x = r+my mod N now, with x2 - m2y2 = F mod N, to get:
(r+my)2 - m2y2 = F mod N
Multiplying out: r2 + 2rmy + m2y2 - m2y2 = F mod N
So have simply: r2 + 2rmy = F mod N, so also: F = r(r + 2my) mod N
Now will have F self-referencing itself with two control variables n and d, where F0 is initial F value, and y0 is initial y:
F = r(r + 2m(y0 + d)) mod N
nF0 = nr(r + 2my0) mod N
So can subtract to get: nF0 - F = r(n(r + 2my0) - r -2m(y0 + d)) mod N
Which is: nF0 - F = r[(n-1)(r + 2my0) - 2md] mod N
And now can use that nF0 - F = 1 mod N will exist.
And using that: 1 = r[(n-1)(r + 2my0) - 2md] mod N, and can get to my modular inverse with:
r-1 = (n-1)(r + 2my0) - 2md mod N
Notice then: nF0 = F+1 mod N does put some pressure on the math. For instance if factors are shared between F0 and N, then those would have to divide off. As yeah, F is being found so that these things are true.
And can again go to F = r(r+2my) mod N, where multiply times r-1 mod N, to get:
Fr-1 = r+2my mod N
Which is true in general, but now with my solution for r-1 mod N want to use with F0 to get:
F0[(n-1)(r + 2my0) - 2md] = r+2my0 mod N
Where can simplify to:
2mdF0 = [F0(n-1) - 1](r+2my0) mod N
Which is a lot more detail to add to what I derive here.
As a simple example consider: N = 101, r = 35
I pick m = 11, and y0 = 2 mod 101.
Then F0 = 35(35 + 2(11)(2)) mod 101 = 35(79) mod 101 = 38 mod 101
And now can relate n and d to each other:
2(11)(38)d = [(38(n-1) - 1](35 + 2(11)(2)) mod 101
so: 28d = [38n - 38 - 1]*79 mod 101 = 73n - 51 mod 101
So: 28d = 73n - 51 mod 101
Where a neat trick is that 28d = 73n - 51 will work! And n and d are otherwise free to be whatever so can solve for that, where notice can find with:
0 = 17n - 23 mod 28, so: 17n = 23 mod 28
So can recurse, looking for modular inverse of 17 modulo 28. Point of showing is to notice how you get to recursion, and to emphasize that with next iteration the modulus must be smaller, as now down from 101 to 28. Oh yeah, also then can cut at least in half, guaranteed--with each recursion.
That is because with modular can use positive or negative. Like as continue with the example notice how can go negative to further shrink things a bit with:
-11n = -5 mod 28, so: 11n = 5 mod 28
Yeah can see that n = 3 works there, which gives d = 6.
Plugging into our expression for modular inverse then:
r-1 = (3-1)(35 + 2(11)(2)) - 2(11)(6) mod 101 = 57 - 31 mod 101 = 26 mod 101
Also, notice that stepping y forward 8, so d = 8, gives:
F = 35(35 + 2(11)(2 + 8)) mod 101 = 35(35 + 22(10)) mod 101 = 35(53) mod 101 = 37 mod 101
Where picked those values because then F0 - F = 1 mod 101, so n = 1 mod 101.
And yup, r-1 = -2(11)(8) mod 101 = -75 mod 101 = 26 mod 101
So yeah, more than one n and d can work for the final answer.
Of course will give same answer, and indeed, 26(35) = 1 mod 101.
Decided should show that path that leads to recursion to highlight the full method to show why is complete.
Notice YOU get to pick m and y0, where notice m has to be coprime to r. This post was more me emphasizing the meta aspect, as is intriguing to me that this approach works by having the equation for F reference itself. Is SO cool.
That is so weirdly easy, huh? These are the kinds of things really make me wonder.
Our species could have gone through its entire existence and never found it.
That really rattles me more than I like to admit. Especially as contemplate more than a year after finding, in a world where some appear to think they can ignore major mathematical discovery.
With some people there is just no respect for knowledge.
To me? They're funny. I get to have the last word. Being the discoverer DOES have its perks.
My words will echo through the rest of human history. That rattles me even more. So I must state to help me accept. It is also a responsibility. Yeah I'm going to go back now to NOT thinking about that too much.
There are two primary ways previously known to calculate the modular inverse, where have talked that in a prior post.
But now humanity knows a third.
James Harris
