Translate

Saturday, December 30, 2017

Modular inverse and pondering obvious

We understandably have few opportunities as a species to ponder obvious things which somehow escaped us, until they did not, as how do we know what we do not know? Infinite knowledge exists. Humanity will only learn, so much.

Emotionally much shifted for me in 2017 which was in many ways my most satisfying discovery year ever, as found my own way to calculate a modular inverse!!! But was such a clean and simple result as well, like a simple gift from the math, to our species. But how could something so easy be missed for so long? Here will talk a simpler start to the path to finding it, which I did not use.

Like consider: x2 - Dy2 = F

Is a fundamental equation. Is known you can reduce other binary quadratic Diophantine equations to it, and I DID have my own most general method for so doing. But still didn't occur to me just thinking about it to consider it modularly:

x2 - Dy2 = F mod N

And yeah I don't bother with congruence symbol as to me is tedious unnecessary extra. And now why not realize that the D with Diophantine equations MAY be a quadratic residue modulo N? Let's assume it is, and let the residue that is squared be m, so have:

D = m2 mod N

So: (x-my)(x+my) = x2 - Dy2 = F mod N, and you can consider some residue r, and notice something useful.

If: x-my = r mod N, then: x+my = Fr-1 mod N, or vice versa as can shift r.

So the modular inverse pops up! Also you can solve for x and y, to solve modulary, which is where I focused for years. But why not naturally ask, can I solve for the modular inverse from there? Answer is, yes. Adventurous readers can test math ability by trying to solve for the modular inverse from THIS point, if can. If you struggle, can just check my derivation.

Where we got there, quick and easy, doing things that apparently human beings do not tend to do!!! But why not? I didn't even take that quick and easy path years ago. Figured it out after.

If still haven't seen my method in action, you might want to check out a post with a full iterative example where I find the modular inverse of 101 modulo 1517, which is 751. 101(751) = 1 mod 1517.

Found myself curious enough tried to work back, and came to conclusion had figured out solution for x and y modularly by September 28, 2012, and traced back best I could with this post on my math group.

Yet wasn't until May of THIS year that I wondered if could do something to find the modular inverse with that, and posted one day with some musings:

Chasing modular inverse

Oh, wow, so that's dated May 5th, which is the date of discovery. Then days later on May 9th posted something cleaner, and have used that date as forgot:

Modular inverse innovation

Ooh, good thing making this post! So was May 5th when had discovery. But May 9th post I just think presents better.

So why new?

Because human beings think certain ways which can miss things. But how do we know what we do not know? We get to know what we mysteriously didn't know, when our species finally learns it. And discovery is not something we fully understand. But should be something we respect.

And make no mistake, a third primary way to calculate the modular inverse is a really big deal.

For me was a puzzle why was left for me to find, but at least removed doubt from people without a clue, who maybe relied on faith in human beings.

So is a perfect litmus test. Like reality finally felt sorry for some of you.

If you understand mathematics in actuality, you know to go with the math, always.

If instead, you simply trust humans? What's wrong with you?

For those who think they love mathematics, who cannot be convinced by math, you need to go into politics or something else as mathematics, then is NOT your area.

For me was just really cool. Was nice to have such a simple and clean result, and figured with an applied and pure math result maybe other things might change. With a history of major discoveries, will admit you do get a different attitude. To me now, major discoveries are very emotional yes. And extremely satisfying, but also, so very curious.


James Harris

No comments: