Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: Ostap Bender on 6 Jun 2010 17:40 On Jun 6, 2:27 pm, JSH <jst...(a)gmail.com> wrote: > On Jun 6, 1:51 pm, Mark Murray <w.h.o...(a)example.com> wrote: > > > > > On 06/06/2010 18:52, JSH wrote: > > > > On Jun 6, 9:48 am, Mark Murray<w.h.o...(a)example.com> wrote: > > >> On 06/06/2010 16:26, JSH wrote: > > > >>> Yes, it is. And yes I could so demonstrate. > > > >>> I've written a Java program that will do quartics because that was > > >>> easier. INTERESTED people can find it at mymathgroup: > > > >>>http://groups.google.com/group/mymathgroup/files?hl=en > > > >> That program does it with a_3 = a_4 = f_3 = f_4 = 1. > > > > Because you pick the a's, so I can pick 1, though I'd think that makes > > > it less efficient to hold those variables constant. And f_3 = f_4 = 1 > > > are still factors because 1 is a factor. > > > OK. > > > On your blog you say > > > <quote> > > Given a quartic residue q mod N, to be solved one can find k, where > > > k^4 = q mod N, from > > > k = (a_1 + a_2 + a_3 + a_4)^{-1} (f_1 + f_2 + f_3 + f_4) mod N > > > where f_1 f_2 f_3 f_4 = T, and T = a_1 a_2 a_3 a_4 q mod N > > > and the a's are free variables as long as they are non-zero and their > > sum is coprime to N. > > > </quote> > > > So the a_i's can be anything nonzero, right? (or did you mean > > integer only?) > > > I'll generalise the above result by saying (using a Maple-like syntax > > and using order m instead of 4): > > > T = mult(f[i], i = 1 .. m) = q mult(a[i], i = 1 .. m) (mod N) (1) > > > A bit later you say (and I paraphrase here a bit while generalising > > from order 4 to order m) > > > <quote mode="paraphrase"> > > f_n = a_n k (mod N) > > </quote> > > > So I write (1) as (and ignoring the superfluous T) > > > mult(k a[i], i = 1 .. m) = q mult(a[i], i = 1 .. m) (mod N) > > k^m mult(a[i], i = 1 .. m) = q mult(a[i], i = 1 .. m) (mod N) > > > you now conclude that > > > k^m = q (mod N) > > > assuming the mult(...) can be divided off. But can it? What > > are the requirements on mult(a[i], i = 1 .. m)? Is a non- > > integer result sensible? > > > You now say that > > > <quote> > > But adding them together gives > > > (f_1 + f_2 + f_3 + f_4) = (a_1 + a_2 + a_3 + a_4) k (mod N) > > > and solving for k is easy enough. > > </quote> > > > I'll rewrite that as > > > sum(f[i], i = 1 .. m) = sum(a[i], i = 1 .. m) (mod N) > > > But you defined f[i] = a[i] k, so > > > sum(k a[i], i = 1 .. m) = sum(a[i], i = 1 .. m) (mod N) > > k sum(a[i], i = 1 .. m) = sum(a[i], i = 1 .. m) (mod N) > > > Now what? > > > k = 1 (mod N) ? > > > This assumes the division is valid again. > > > But (mod N) is handled by a congruence relation on the integers. > > We have addition, subtraction and multiplication, but NO DIVISION. > > You bodge this by saying sum(a[i], i = 1 .. m) must be coprime > > to N (at least that's what I'm guessing you are getting at). You > > don't mention that sum(a[i], i = 1 .. m) must be <> 0 for all m. > > > So; > > > 1) f_i's are extraneous as f_i = k a_i > > 20 sum(a[i], i = 1 .. m) <> 0 for all m. > > > For k^m = q (mod N) you still have m variables (the a_i set). > > They are somewhat arbitrary, as you point out, and as you just > > pick-and-choose some of them, it means you have an answer space > > that is huge. > > > No wonder people don't talk about this. Its trivial. Wait; > > didn't you already say that? > > It IS trivially derived. > > > What else haven't you checked? Apart from the literature? > > Who cares? You're an idiot. I hate your type of posts as you waste > so many people's time. > > I already noted it's trivially derived. I think it's something that > Gauss probably knew. > > However, it's also a way to solve for k, when k^m = q mod N, by > factoring. On Jun 6, 8:26 am, JSH <jst...(a)gmail.com> wrote: > On Jun 6, 3:14 am, hagman <goo...(a)von-eitzen.de> wrote: > > > And what makes this method notably faster than simply triyng > > k=1,2, ..., N-1? > > I didn't say it was notably faster. Are you saying it's not? > > > Note that this brute force runs in O(N) time and O(1) space. > > How fast is your stuff? > > Don't know. It's an open research question. > > > Could you demonstrate your idea with a trivial example like > > k^2349167 = 29166469829073 mod 5570560728995753? > > That's not trivial. Wait. Didn't you just write: > However, it's also a way to solve for k, when k^m = q mod N, by > factoring. If so - what is preventing you from coding your algorithm in java, solving k^2349167 = 29166469829073 mod 5570560728995753, and posting the list of solutions? > Now you screwed over anyone who is curious about what may or may not > be known around this result with an idiotic post babbling all over the > map to say nothing at all and you wonder why Usenet can be so freaking > useless? > > You DID THAT ON PURPOSE just to try and confuse people. > > You are such a stupid idiot but you stalk my postings and infuriate > me!!! > > And THAT is the point, right? > > You know you can push my buttons. You're probably going somewhere to > jack off now, after you read this post, and drool with hot nasty lust > about your latest success on sci.math at PISSING ME OFF!!! On Jun 5, 10:16 am, JSH <jst...(a)gmail.com> wrote: > While I'd prefer to stay away from the hostility... No, you wouldn't. You live to insult other people.
From: Mark Murray on 6 Jun 2010 17:51 On 06/06/2010 22:27, JSH wrote: >> No wonder people don't talk about this. Its trivial. Wait; >> didn't you already say that? > > It IS trivially derived. > >> What else haven't you checked? Apart from the literature? > > Who cares? You're an idiot. I hate your type of posts as you waste > so many people's time. > > I already noted it's trivially derived. I think it's something that > Gauss probably knew. > > However, it's also a way to solve for k, when k^m = q mod N, by > factoring. Except you don't show that. You show a badly presented argument showing how (with a sufficiently large number of variables) the sum of said variables can have a relationship with the product of the same variables. Then you started crowing about earth-shattering discoveries, your submission of this to a journal, the usual corruption of mathematicians and national security influence/interest. > Now you screwed over anyone who is curious about what may or may not > be known around this result with an idiotic post babbling all over the > map to say nothing at all and you wonder why Usenet can be so freaking > useless? "Anyone"? No. This is reserved for YOU. > You DID THAT ON PURPOSE just to try and confuse people. I did it ON PURPOSE to show that you were deluded as to the relative importance of this work. > You are such a stupid idiot but you stalk my postings and infuriate > me!!! The truth hurts, no? > And THAT is the point, right? Infuriating you is a side effect. Debating with you is the point. > You know you can push my buttons. You're probably going somewhere to > jack off now, after you read this post, and drool with hot nasty lust > about your latest success on sci.math at PISSING ME OFF!!! Fantasise away. But if it annoys you to believe that I am enjoying your anger, then it must be the easiest thing in the world to edit the angry bits out, no? Then, that should annoy ne instead, because I would't be getting my "fix" then. Easy. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: JSH on 6 Jun 2010 18:06 On Jun 6, 2:51 pm, Mark Murray <w.h.o...(a)example.com> wrote: > On 06/06/2010 22:27, JSH wrote: > > >> No wonder people don't talk about this. Its trivial. Wait; > >> didn't you already say that? > > > It IS trivially derived. > > >> What else haven't you checked? Apart from the literature? > > > Who cares? You're an idiot. I hate your type of posts as you waste > > so many people's time. > > > I already noted it's trivially derived. I think it's something that > > Gauss probably knew. > > > However, it's also a way to solve for k, when k^m = q mod N, by > > factoring. > > Except you don't show that. That's the trivial part. You admitted yourself it's trivial. Now you claim it's not shown? You ARE an idiot. > You show a badly presented argument showing how (with a sufficiently > large number of variables) the sum of said variables can have a > relationship with the product of the same variables. That is, I show that you can find k, when k^m = q mod N, by factoring. You're trying to distract readers which is stupid. The paper went to the Annals. I've emailed mathematicians directly all over the world. After these posts, I've recently noted bursts of activity on my math blog from several countries, specifically Germany. What you say here is not necessarily going to block this result. Your relevance has to do with: was this result known before? As trying to convince that factoring to solve k^m = q mod N isn't of any interest at all in the modern world is the essence of grasping, and proves another point I've often made: people like you fight the human species deliberately, trying to block the human race itself. One reason why years ago I wondered if you were aliens, as what kind of human being could do such a thing? People like you is the answer, as now I think you're human. Just a very lost soul. James Harris
From: Tim Peters on 6 Jun 2010 18:44 [JSH] >> ... >> 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. >> >> It's trivially derived by noting that if you have >> >> f_1 = a_1*k mod N thru f_m = a_m*k mod N >> >> multiplying them together gives f_1*...*f_m = a_1*...*a_m*k^m >> a_1*...*a_m*q mod N. >> >> But *adding* them together gives (f_1+...+ f_m) = (a_1+...+a_m)*k mod >> N, and solving for k is easy enough. >> ... [hagman] > And what makes this method notably faster than simply triyng > k=1,2, ..., N-1? > Note that this brute force runs in O(N) time and O(1) space. > How fast is your stuff? > Could you demonstrate your idea with a trivial example like > k^2349167 = 29166469829073 mod 5570560728995753? > Or at least an even more trivial example like > k^3 = 973 mod 1073? > The latter should be doable by hand with your method Well, for the second example, let's pick the a_i to be the first 3 primes: a1 = 2 a2 = 3 a3 = 5 Then pick these (just for example): f1 = 568 f2 = 852 f3 = 347 Then you can easify verify (showing a Python shell here): >>> a1 + a2 + a3 10 >>> 10 * 322 % N # showing that 322 is 10's inverse mod 1073 1 >>> 322 * (f1 + f2 + f3) % N # this should be k 284 >>> pow(284, 3, N) # verifying - pow(a, b, c) is an efficient a^b mod N 973 The first example is much too tedious to do in the same style ;-)
From: Ostap Bender on 6 Jun 2010 19:49
On Jun 6, 3:06 pm, JSH <jst...(a)gmail.com> wrote: > On Jun 6, 2:51 pm, Mark Murray <w.h.o...(a)example.com> wrote: > > > On 06/06/2010 22:27, JSH wrote: > > > >> No wonder people don't talk about this. Its trivial. Wait; > > >> didn't you already say that? > > > > It IS trivially derived. > > > >> What else haven't you checked? Apart from the literature? > > > > Who cares? You're an idiot. I hate your type of posts as you waste > > > so many people's time. > > > > I already noted it's trivially derived. I think it's something that > > > Gauss probably knew. > > > > However, it's also a way to solve for k, when k^m = q mod N, by > > > factoring. > > > Except you don't show that. > > That's the trivial part. You admitted yourself it's trivial. Now you > claim it's not shown? > > You ARE an idiot. No, he is not. You think so only because you lack the intelligence to recognize intelligence. > > You show a badly presented argument showing how (with a sufficiently > > large number of variables) the sum of said variables can have a > > relationship with the product of the same variables. > > That is, I show that you can find k, when k^m = q mod N, by factoring. > > You're trying to distract readers which is stupid. The paper went to > the Annals. Annals of what? How much do you want to bet that your paper will not be deemed worthy of publishing there? > I've emailed mathematicians directly all over the world. What does this prove? That you know how to use email? But nobody is saying that you are so stupid as not to be able to send emails. It is assumed that you are smart enough for that. Otherwise, you wouldn't have been able to post to Usenet either. > After these posts, I've recently noted bursts of activity on my math > blog from several countries, specifically Germany. Germany produces few good comedians, so Germans always search for sources of laughter. > What you say here is not necessarily going to block this result. Haven't you been pestering sci.math and individual math professors with your nonsense for many years now, without finding anybody to pay attention to you? How much are you willing to bet that the same will happen this time too? > Your relevance has to do with: was this result known before? He told you "yes" and gave you a Knuth et al reference. Have you read it yet? > As trying to convince that factoring to solve k^m = q mod N isn't of > any interest at all in the modern world is the essence of grasping, > and proves another point I've often made: people like you fight the > human species deliberately, trying to block the human race itself. Actually, factoring is a very important area of research, especially because of its relevance to public-key cryptography. If you ever discover anything non-trivial about factoring - you will be published, or some corporation will pay you $millions for your discovery. But how much do you want to bet that it won't happen to you? |