Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: JSH on 6 Jun 2010 13:52 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. > How does that qualify as "doing quartics"? The program solves for k, when k^4 = q mod N, and it adjusts only a few variables because that was easier than writing a more complex program that shifts all of them, and probably unnecessary for a quick look at this basic research level. Presumably it's less efficient as a result. James Harris
From: Joshua Cranmer on 6 Jun 2010 15:01 On 06/06/2010 11:26 AM, JSH wrote: > It's zipped at QuarticRes.zip and is a quick and dirty try and just > putting something together to try and answer some questions. Any particular reason you're using Java 1.2 instead of Java 6? There are many other comments I could make on your source code... -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: JSH on 6 Jun 2010 16:10 On Jun 6, 12:01 pm, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > On 06/06/2010 11:26 AM, JSH wrote: > > > It's zipped at QuarticRes.zip and is a quick and dirty try and just > > putting something together to try and answer some questions. > > Any particular reason you're using Java 1.2 instead of Java 6? Why not? Hey it works... > There are many other comments I could make on your source code... Geek.
From: Mark Murray on 6 Jun 2010 16:51 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? What else haven't you checked? Apart from the literature? M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: JSH on 6 Jun 2010 17:27
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. 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!!! James Harris |