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: Mark Murray on 13 Jun 2010 17:08 On 13/06/2010 22:00, JSH wrote: > Military members who later learn of the real risk may wish to thank > you in person later. > > I will, of course, not comply. Didn't think you would. Nor did I think you'd have an original excuse. This has nothing to do with the military. You just can't do it. > I've sent an update to the Annals of Mathematics. Good for you. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: JSH on 14 Jun 2010 21:11 On Jun 12, 7:27 pm, JSH <jst...(a)gmail.com> wrote: > 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. The responses to this result were rather odd. Besides this result there is no way known in general to find k, when k^m = q mod N, with m, a natural number besides brute force. One persistent poster from sci.math who stalked me over to this group "Mark Murray" speciously claims it's equivalent to brute force but gave no support for that claim. What more do you need? It's a trivially proven result in modular arithmetic that shows a direct relation to factoring and finding k, when k^m = q mod N, so it solves one of the most fundamental problems in modular arithmetic in a surprising and simple way. What? Don't believe such a simple result could actually exist? Or believe that something so simple can't be important? What? I'm at a loss here. Sure, say I've made big claims before, but so what? Who listens to what people *say* anyway in terms of BIG CLAIMS, when you can just look at a math equation. Or do you consider the source before you look at a mathematical result? I'm curious as to what's going on here. James Harris
From: Mark Murray on 15 Jun 2010 02:48 On 15/06/2010 02:11, JSH wrote: > Besides this result there is no way known in general to find k, when > k^m = q mod N, with m, a natural number besides brute force. One > persistent poster from sci.math who stalked me over to this group > "Mark Murray" speciously claims it's equivalent to brute force but > gave no support for that claim. I cited your solution, which was a Java program, which used brute force. > What more do you need? A solution better than brute force. > It's a trivially proven result in modular arithmetic that shows a > direct relation to factoring and finding k, when k^m = q mod N, so it > solves one of the most fundamental problems in modular arithmetic in a > surprising and simple way. Fine - lets pretend that there IS this relation between factoring and finding k. Find a significant k without chickening out. > What? Don't believe such a simple result could actually exist? Or > believe that something so simple can't be important? I'll concede it may exist. I've never conceded that it is non-trivial (the relationship) or useful (actually solvable for "real" problems). > What? I'm at a loss here. That much is obvious. > Sure, say I've made big claims before, but so what? Who listens to > what people *say* anyway in terms of BIG CLAIMS, when you can just > look at a math equation. Or do you consider the source before you > look at a mathematical result? k = pq where k, p and q are integers and p and q are LARGE primes shows a trivial relationship between p, q and k. If all you know is k, finding p and q is HARD. > I'm curious as to what's going on here. You are failing to understand the consequences of basic mathematics. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: JSH on 15 Jun 2010 10:14 On Jun 14, 11:48 pm, Mark Murray <w.h.o...(a)example.com> wrote: > On 15/06/2010 02:11, JSH wrote: > > > Besides this result there is no way known in general to find k, when > > k^m = q mod N, with m, a natural number besides brute force. One > > persistent poster from sci.math who stalked me over to this group > > "Mark Murray" speciously claims it's equivalent to brute force but > > gave no support for that claim. > > I cited your solution, which was a Java program, which used brute force. Why would that be significant? Have you actually *looked* at the equations in the post that starts this thread? Or are you just hounding me in replies without thinking? ___JSH
From: Mark Murray on 15 Jun 2010 13:33
On 15/06/2010 15:14, JSH wrote: >> I cited your solution, which was a Java program, which used brute force. > > Why would that be significant? Have you actually *looked* at the > equations in the post that starts this thread? I have looked at the equations. I posted some detail about them too. As for significance, the result you cite is (as you admit) trivial. Solutions, however, are not efficient, and you are (yet again) trumpeting the downfall of civilisation without the faintest notion that this method won't make a jot of difference. > Or are you just hounding me in replies without thinking? Nope. I'm pointing out your lack of thinking. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist. |