General factoring result for k^m = q mod N
in [Cryptography]
|
Prev: The Winds of Change - The Three Snake Oils of Cryptography.
Next: Current state of affairs in cryptanalysis: an observation
From: JSH on 12 Jun 2010 22:27 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. James Harris
From: amzoti on 12 Jun 2010 23:13 On Jun 12, 7:27 pm, JSH <jst...(a)gmail.com> wrote: > > James Harris Delusional narcissist! You are a cheat, liar and charlatan. No one here is going to buy your snake oil. Magnanimous claims and zero to show for it.
From: Mark Murray on 13 Jun 2010 06:21 On 13/06/2010 03:27, JSH wrote: > Yet I'm the one who found it, over 200 years since Gauss introduced > "mod" in 1801. 1) Chinese remainder theorem. 2) Modular exponentiation. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: JSH on 13 Jun 2010 10:36 On Jun 13, 3:21 am, Mark Murray <w.h.o...(a)example.com> wrote: > On 13/06/2010 03:27, JSH wrote: > > Yet I'm the one who found it, over 200 years since Gauss introduced > > "mod" in 1801. > > 1) Chinese remainder theorem. > > 2) Modular exponentiation. Interesting, chased the link to Wikipedia for modular exponentiation and that got me to wondering my result could be used to find e. Given c = b^e mod m, where c, b and m are known, yeah, it seems to me that is should, potentially, maybe be possible using my result to figure out e. But maybe not. I decided to stop thinking on it after a point. Kind of overwhelming. So the rest may not be valid, but I have to toss it out there anyway for national security reasons, as the "unknown" is not good. It's bad. Cool. Well guess that breaks something in encryption. NSA should start looking for a new method, fast. Thanks "Mark Murray"! I hadn't realized that route existed. So you've helped reveal a new potential vulnerability. And on the appropriate newsgroup! Yuck. This result then potentially breaks all known encryption schemes around modular arithmetic, that involve integer factorization or discrete logarithms, which is what a foundation level result can give you. British and American mathematicians ignore this result--if it does, still not sure but for national security reasons will leave this message in here--at their peril as of course people in other countries may have no reason to acknowledge that they know of this result, especially to take down the big arrogant boys who claim to be at the top of the heap. James Harris
From: Tom St Denis on 13 Jun 2010 11:12
On Jun 13, 10:36 am, JSH <jst...(a)gmail.com> wrote: > Given c = b^e mod m, where c, b and m are known, yeah, it seems to me > that is should, potentially, maybe be possible using my result to > figure out e. But maybe not. I decided to stop thinking on it after "not" ... understatement of this century. > Cool. Well guess that breaks something in encryption. NSA should > start looking for a new method, fast. I don't get how this follows, and I think that's what makes you "special." You admit your idea is probably bunk, but then conclude that it's a valid result afterall with no justification whatsoever. Tom |