Saturday, June 12, 2010
General factoring result for k^m = q mod N
Oddly enough a fairly simple general result relates finding k, when k^m = q mod N, where m is a natural number to factoring.
Given an mth residue where m is a natural number, q mod N, to be solved one can find k, where
k^m = q mod N, from
k = (a_1+a_2+...+a_m)^{-1} (f_1 +...+ f_m) mod N
where f_1*...*f_m = T, and T = a_1*...*a_m*q mod N
and the a's are free variables as long as they are non-zero and their sum is coprime to N.
So you get some T, such that T = a_1*...*a_m*q mod N, factor it, and you may have k using its factors with that simple relation.
It's a general result, which may have been known to Gauss and simply didn't get written down, or maybe he did and no one noticed. It's not the sort of thing that had the importance in the past that it MAY have in our modern age of computers and systems based on factoring as a hard problem.
I actually generalized to the full result about a month ago, having in the past on this newsgroup mentioned a simpler quadratic result that I noticed first!
I think some posters derided it as too simple and they moved on. I puzzled over it a few more months and realized that I could generalize to m, a Natural number.
As it is a general result it's hard to say much about how it works, especially with m greater than 2. It has intriguing behavior though even with the quadratic case.
I'll admit is is a sobering find for me, as it's an incredibly simple result to prove, is general for residues connecting them to integer factorization in a deep way, and looks like the kind of result one would expect to be in the front of a number theory textbook on modular arithmetic.
Yet I'm the one who found it, over 200 years since Gauss introduced "mod" in 1801.
Ok, I'll stop there. I won't be surprised to see a lot of hateful and hostile replies in response. I've been talking it out on sci.math and have been ripped on continuously. The insult-fest never ends on Usenet though. That's part of what defines Usenet.
No matter what, someone insults you.
Given an mth residue where m is a natural number, q mod N, to be solved one can find k, where
k^m = q mod N, from
k = (a_1+a_2+...+a_m)^{-1} (f_1 +...+ f_m) mod N
where f_1*...*f_m = T, and T = a_1*...*a_m*q mod N
and the a's are free variables as long as they are non-zero and their sum is coprime to N.
So you get some T, such that T = a_1*...*a_m*q mod N, factor it, and you may have k using its factors with that simple relation.
It's a general result, which may have been known to Gauss and simply didn't get written down, or maybe he did and no one noticed. It's not the sort of thing that had the importance in the past that it MAY have in our modern age of computers and systems based on factoring as a hard problem.
I actually generalized to the full result about a month ago, having in the past on this newsgroup mentioned a simpler quadratic result that I noticed first!
I think some posters derided it as too simple and they moved on. I puzzled over it a few more months and realized that I could generalize to m, a Natural number.
As it is a general result it's hard to say much about how it works, especially with m greater than 2. It has intriguing behavior though even with the quadratic case.
I'll admit is is a sobering find for me, as it's an incredibly simple result to prove, is general for residues connecting them to integer factorization in a deep way, and looks like the kind of result one would expect to be in the front of a number theory textbook on modular arithmetic.
Yet I'm the one who found it, over 200 years since Gauss introduced "mod" in 1801.
Ok, I'll stop there. I won't be surprised to see a lot of hateful and hostile replies in response. I've been talking it out on sci.math and have been ripped on continuously. The insult-fest never ends on Usenet though. That's part of what defines Usenet.
No matter what, someone insults you.
# posted by James Harris @ 22:28 
