Some Math
Global resource of innovative mathematical ideas. Discovery for the 21st century. Abstract reductionism realized. And modular rules.
Translate
Tuesday, March 05, 2024
Can check with AI
Saturday, February 10, 2024
Finding modular inverse simplified
Back in 2017 found a new way to calculate the modular inverse giving world a third one along with method by Euler and extended Euclidean algorithm.
Will give a simplified version which I use. So is my usual approach where can adjust of course if notice an area can improve.
And I just use equals rather than congruence symbol.
To get modular inverse of r modulo N, first pick k for F0 = rk mod N such that rk is greater than N such that F0 and N do not share prime factors.
Then have unknowns d and n where:
F0 d = [F0 n - (F0 + 1)]k mod N
You solve for d often by recursion, so can divide off F0 as can now get:
0 = (F0 kn) mod N - [(F0 + 1)k] mod N mod F0
If F0 k though is less than N subtract N which is required to prevent F0 from still being a factor. Which means can have a new modular inverse to find but now where F0 is modulus, so shrank.
Recurse until have an inverse and then roll up to get n. Usually takes me one or two recursions but like studying small primes.
When have solved for n, you get modular inverse of r from:
r-1 = (n-1)k - d mod N
Now will do an example to demonstrate.
With N = 137, will find modular inverse of 53.
Already have done from some research was doing so can just copy over. Picking k = 3 as is smallest multiple that gets 53 greater than 137.
F0 = 53(3) = 22 mod 137
22d = (22n - 23)(3) = 66n - 69 mod 137
So need to subtract to get:
22d = -71n - 69 mod 137, so: 0 = -5n - 3 mod 22
5n = -3 = 19 mod 22 and can recurse now to find modular inverse of 5. Picking k' = 5 and 5(5) = 3 mod 22.
So: 3d' = (3n' - 4)(5) mod 22, so: 3d' = 15n' - 20 mod 22
And subtract 22 to get: 3d' = -7n' - 20 mod 22
So: 0 = -n' - 2 = 0 mod 3, giving n' = 1.
Then: 3d' = -7(1) - 20 = -27; d'= -9
So: 5-1 = (1-1)(5) - (-9) = 9 mod 22
So now I just use to get:
n = 9(19) mod 22, so n = 17
So: 22d = -71(17) - 69 = -1276
Where now can divide off 22, and you have: d = -58 mod 137
Then 53-1 = (17-1)(3) - (-58) = 106 mod 137
And yup, 53(106) = 1 mod 137.
That is my simplified approach. Can also use full system where get a few more symbols. I give that and derivation in post: Modular inverse innovation
Friday, February 03, 2023
Playing with integers
Much of my life just liked playing with numbers where was usually integers. Enjoying fun details like knowing 1152 must be divisible by 9 as digits sum to it. But I got frustrated trying to read up on what was called discrete math as was so abstruse and complicated.
Now decades later have introduced true modular algebra with lots of easy tools for just playing with integers. And yeah my own research these days is using tools I already have, so here is a reference. I come to this blog to refresh and check what's trending for popular posts.
If new to my research might need my take on modular arithmetic where gives my style. And I play with actual integers so theory gets shown by examples. One of my favorite show-off pages is: So much from one thing
Must note am NOT a mathematician! Talk that quite a bit so will not go into much yet again. Am a person who likes playing with numbers who did my own research. I am very disappointed with modern mathematical folks and don't bother with them.
Glad can just give my ideas for interested people thanks to the web.
Tuesday, December 27, 2022
Math is better for comfort
Friday, December 02, 2022
Reassurance with my math
Finally found myself just playing around with my method for finding a modular inverse and was reassuring. Math is that way. Doing a post to let know am still active and to show it again.
So will calculate modular inverse of 19 mod 1001 which is 7(11)(13).
Let 2m = 1 mod 1001, then F0 = 19(19 + y0) mod 1001. Can pick y0 = 34. Then F0 = 6 mod 1001. That was lucky! Can pick whatever I like.
Picking so that F0 is as small as possible without 19 as a factor but coprime to 1001, and usually regardless have found need to recurse with coefficient of d as new modulus.
6d = (6n - 7)(53) mod 1001
6d = 318n - 371 mod 1001
And 6(167) = 1002 = 1 mod 1001 which is very convenient.
So: d = 53n - 896 mod 1001, so can use n = 1 and then d = -843. So 19-1 = 843 mod 1001.
Those values worked better than I expected, as of course really like easy. But yeah is very reassuring to just do some math and get the correct answer.
My way makes calculating the modular inverse so straightforward.
Am still active on this blog but often just reviewing. Have a lot of research results! Can play around endlessly with them.