Wednesday, December 06, 2017

My modular inverse method

Discovered there was a third primary way to figure out the modular inverse, which is NOT related to work by Euler or in any way to Euclidean algorithm.

Like to talk as a system, where that system is:

 r-1 = (n-1)(r + 2my0) - 2md mod N

Where y0 is chosen as is m, with m not equal to r, and n and d are to be determined. They are found from:

2mdF0 = [F0(n-1) - 1](r + 2my0) mod N


F0 = r(r+2my0) mod N


When using have focused on two coefficients as key in an equation with two unknowns so you have a degree of freedom.

Those key coefficients are given by: 2mF0 mod N and F0(r+2my0) mod N

Like with my detailed modular inverse example in this post, where calculate the modular inverse of 101 modulo 1517.

So r = 101, N = 1517. Then I get to make arbitrary choices for m and y0 where maybe future research will give more guidelines there. And choose m = 47, and y0 = 1 as is easy.

Plugging those in and you can get detailed calculation at referred post, reach:

295d = 499n + 162 mod 1517

Here you can see those key coefficients as one is 295 and the other is 499.

So with d and n, the two unknowns, I can just pick for one so that I can solve for the other.

What I do is choose n such that 295 divides across as I want to pick a smaller value, as yup, need another modular inverse. And show how to recurse with my detailed example. Ultimately finding that d = 190 mod 1517 and n = 112 mod 1517. And you end up with correct answer that modular inverse of 101 modulo 1517 is 751.

There is one area where people can mess up, which is if you make a mistake with modular arithmetic as to how to divide across factors shared with the modulus.

So yeah, is a full method, with which you can use in general to solve for the modular inverse, though practical details of a full algorithm are not things I focus on. But immediately realized, as someone with coding experience that you can multi-thread effectively.

With other techniques, when I look at them, is like, what's the point? But with my system you have choice, which can shrink those key coefficients, and also you can loop down paths which split by choice. And if have multiple such paths, presumably some will be shorter and a smart algorithm could maybe figure out better ways? Or you can just run several at a time and use one which reaches answer first, of course.

Is advancement of human knowledge at foundation level of number theory which is at the earliest stages. Is weird too. No such fundamental result was supposed to be still available to be found. Presumably ALL had been found before. Yet here it is, in our 21st century, less than a year old the discovery.

That is so wild.

James Harris

No comments: