Still giddy over finding my own primary way to calculate the modular inverse thought would talk more in general about the subject.
The modular inverse is simply the number you can multiply times another number to get 1 modulo some other number. Like 2 times 3 equals 6 which is 1 modulo 5.
Succinctly: 2(3) = 1 mod 5
Can also express as: 2 = 3-1 mod 5
Does not always exist though. Like, when prime factors are shared cannot exist. For example, consider 21 mod 33. There is no modular inverse for 21 modulo 33, but divide off the 3, and get: 7 mod 11. And modular inverse is 8, as 7(8) = 1 mod 11.
Using very simple on purpose and also shows, is not complicated. Modular inverse is just a very basic idea in modular algebra, but how do you find?
Fermat and Euler show a way
One cool way to figure it out, goes back to ideas from Fermat, though Euler expanded on. As Fermat is generally credited with noticing that a number raised to a prime power equaled itself modulo that power.
For example if x is that number, and p is the prime: xp = x mod p
What does that have to do with modular inverse?
Well you can divide both sides by x2, and get: xp-2 = x-1 mod p
For example, consider x = 3, and p = 7. Then 35 = 3-1 mod 7. Where we can take that in modular bites, as:
(32)(32)(3) = 3-1 mod 7 = (9)(9)(3) = (2)(2)(3) = 12 mod 7.
Which is 5 mod 7. And yup, 3(5) = 1 mod 7. And Euler got clever and figured out a way to use something other than a prime for the modulus using what is called his totient function. And if wish to pursue further should web search as just a bit too complicated for a quick demonstration here.
Also if don't know already should web search to learn more about Fermat's approach and why is true!
Extended Euclidean algorithm
Other way to calculate modular inverse goes back to ideas from Euclid, with something called the extended Euclidean algorithm. Gist of it is, Euclid taught a way to get the greatest common factor between two numbers. Like between 12 and 15 that number is 3. Turns out the basic approach can also be used with modular inverse. Here is a simple example, calculating modular inverse of 13 modulo 137.
Notice that: 137 = 13(10) + 7 and also that: 7*2 - 1 = 13
So: 7*2 = 1 + 13, and: -13 + 7*2 = 1
Looks weird am sure, but I want that 1, and can substitute now for 7, from first as:
7 = 137 - 13(10), so: -13 + 2(137 - 13(10)) = 1
Since I want modulo 137 can make things easier: -13 - 2(13)(10) = 1 mod 137
And simplify to get: -13 - 13(20) mod 137 = 13(-21) = 13(116) = 1 mod 137
So, 13(116) = 1 is found, and notice just did a few things kind of different, but clever. But unlike before there is no way to know how long that will take to work!
Turns out, key to the quick there is that 137 mod 13 = 7 and 7*2 = 1 mod 13. So was lucky. But you WILL get to something like that eventually with this approach, if no prime factors are shared, otherwise you get to all shared prime factors. You have to find that situation where you get a 1, to find your modular inverse. And if is new to you, and wonder how that works, which is rest of the trick, yup, web search. Am just doing simple and quick here to give an overview of the basic math principles involved.
My way is latest primary way
Besides just going through residues and multiplying out checking which one is modular inverse, which is called using brute force, the two basic approaches above were ALL the primary ones that humanity had. And lots of variations on those themes too as clever people figured out how to do various ways.
Yet regardless, each method for calculating modular inverse traced back to only the two basic or brute force.
Eight months ago though, on May 5th, 2017, introduced the first new basic approach in a LONG time, with a third primary way, and am celebrating that a bit with this post! One of my best explanations I think is:
My modular inverse method
And I've talked a LOT around how I found it, and why that is surprising, as it is.
This post was focused on the other two primary ways for finding the modular inverse.
James Harris
No comments:
Post a Comment