Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: Tim Little on 6 Jun 2010 20:57 On 2010-06-06, JSH <jstevh(a)gmail.com> wrote: > note that mathematicians have no known method for finding k, when > > k^m = q mod N > > where m is a natural number, already, besides the brute force method Incorrect, which you would know if you had any ability or inclination to read even basic resources in number theory. There are no known algorithms that are polynomial in the number of digits involved, which likely confuses you since you don't know the difference and refuse to learn. > which the poster actually MENTIONS as if mindlessly trying every k, > taking it to the mth power, and seeing if you have q residue is > actually a competing idea. It does compete favourably with your method, as your method is slower. - Tim
From: JSH on 6 Jun 2010 21:20 On Jun 6, 3:23 pm, Ostap Bender <ostap_bender_1...(a)hotmail.com> wrote: > On Jun 6, 2:55 pm, JSH <jst...(a)gmail.com> wrote: > > > > > > > On Jun 6, 2:40 pm, Ostap Bender <ostap_bender_1...(a)hotmail.com> wrote: > > > > 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? > > > That requires factoring some rather large numbers. The simple test > > programs I've written actually factor by brute force using a list of > > all the primes less than 100. > > So, your algorithm can deal with only very small numbers. What use is > it? > > > Obviously it would be inadequate for the task you present. > > How about something of this size: > > k^23467 = 292954073 mod 559135753 > > ? > > > But also Usenet IS a swamp of the math world. You're not important > > here. > > And you choose Usenet as your way of communicating with the math > world? How pathetic of you. > > > You're not in a position to make demands as no one cares in the > > mainstream math world what you think. > > Of course I am not in a position to make demands. But I am in a > perfect position to expose and make fun of clueless, lazy, insulting, > stupid ignoramuses like yourself. > > > I'm using Usenet now to talk about this result with others versus > > talking to myself while I wait, > > Wait for what? > > > and to see if one of you can find > > evidence that it was previously known as a simple result at the heart > > of modular arithmetic SHOULD BE ALREADY KNOWN. > > First of all, you are not in a position to make demands for "one of > us" to find evidence for you. > > Second, Mark Murray did go out of his way and did find evidence for > you: > > ------------------- > > From: Mark Murray <w.h.o...(a)example.com> > Date: Jun 6, 3:21 am > Subject: Solving k^m = q mod N > > If you are not scared of reading books, then look at > "Concrete Mathematics" by Graham, Knuth and Patashnik, ISBN > 0-201-55802-5. In my second edition, Chapter 4 (in particular sections > 4.6 and 4.7 pp 123-128) cover the material you claim is so forgotten. > > ------------------------- > > Have you checked this reference yet? No, I don't have that book. Are you agreeing with him then? So I should buy this book? I'm not going to a library to get it, and I don't see that it's readable online. If you are correct, then yes, you are doing me a big favor, as that's exactly the type of information I need. But just to be sure, you're saying that all I have to do to see my method for finding k, when k^m = q mod N, is buy that book and look at the chapters mentioned? James Harris
From: Ostap Bender on 7 Jun 2010 02:55 On Jun 6, 6:20 pm, JSH <jst...(a)gmail.com> wrote: > On Jun 6, 3:23 pm, Ostap Bender <ostap_bender_1...(a)hotmail.com> wrote: > > > > > On Jun 6, 2:55 pm, JSH <jst...(a)gmail.com> wrote: > > > > On Jun 6, 2:40 pm, Ostap Bender <ostap_bender_1...(a)hotmail.com> wrote: > > > > > 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? > > > > That requires factoring some rather large numbers. The simple test > > > programs I've written actually factor by brute force using a list of > > > all the primes less than 100. > > > So, your algorithm can deal with only very small numbers. What use is > > it? > > > > Obviously it would be inadequate for the task you present. > > > How about something of this size: > > > k^23467 = 292954073 mod 559135753 > > > ? > > > > But also Usenet IS a swamp of the math world. You're not important > > > here. > > > And you choose Usenet as your way of communicating with the math > > world? How pathetic of you. > > > > You're not in a position to make demands as no one cares in the > > > mainstream math world what you think. > > > Of course I am not in a position to make demands. But I am in a > > perfect position to expose and make fun of clueless, lazy, insulting, > > stupid ignoramuses like yourself. > > > > I'm using Usenet now to talk about this result with others versus > > > talking to myself while I wait, > > > Wait for what? > > > > and to see if one of you can find > > > evidence that it was previously known as a simple result at the heart > > > of modular arithmetic SHOULD BE ALREADY KNOWN. > > > First of all, you are not in a position to make demands for "one of > > us" to find evidence for you. > > > Second, Mark Murray did go out of his way and did find evidence for > > you: > > > ------------------- > > > From: Mark Murray <w.h.o...(a)example.com> > > Date: Jun 6, 3:21 am > > Subject: Solving k^m = q mod N > > > If you are not scared of reading books, then look at > > "Concrete Mathematics" by Graham, Knuth and Patashnik, ISBN > > 0-201-55802-5. In my second edition, Chapter 4 (in particular sections > > 4.6 and 4.7 pp 123-128) cover the material you claim is so forgotten. > > > ------------------------- > > > Have you checked this reference yet? > > No, I don't have that book. > > Are you agreeing with him then? I don't have that book either. In fact, I am not an expert on number theoretic algorithms. > So I should buy this book? I'm not going to a library to get it, and > I don't see that it's readable online. It depends on your financial situation. If you have the money - buy the book. If not - going to a college library seems like a good idea. > If you are correct, then yes, you are doing me a big favor, as that's > exactly the type of information I need. Good. Let us know what you think after you read the sections that Mark gave you.
From: MichaelW on 7 Jun 2010 17:00 On Jun 6, 8:21 pm, Mark Murray <w.h.o...(a)example.com> wrote: > On 05/06/2010 18:16, JSH wrote: > > > While I'd prefer to stay away from the hostility, lying, and other > > misinformation threats of Usenet I'm kind of stuck with a surprising > > situation to me around my latest major result, a way to solve for k, > > when k^m = q mod N. > > While you call this "staying away from the hostility, lying, and other > misinformation threats", many others will call it "failure to follow > prior research, read texts or otherwise stay current". > > If your book phobia prevents you from following that route, you can > try going to a search engine and enter the words > > integer modular factorization > > The subject materal is > > If you are not scared of reading books, then look at > "Concrete Mathematics" by Graham, Knuth and Patashnik, ISBN > 0-201-55802-5. In my second edition, Chapter 4 (in particular sections > 4.6 and 4.7 pp 123-128) cover the material you claim is so forgotten. > > M > -- > Mark "No Nickname" Murray > Notable nebbish, extreme generalist. Mark, I am reading the sections you mention. Whilst it talks around some of the issues raised my math fu is insufficient to see an exact match. Are you able to drop a paragraph or two indicating how you would read the text in the light of the original post? Thanks, Michael W.
From: Mark Murray on 7 Jun 2010 18:15
On 07/06/2010 22:00, MichaelW wrote: > I am reading the sections you mention. Whilst it talks around some of > the issues raised my math fu is insufficient to see an exact match. > Are you able to drop a paragraph or two indicating how you would read > the text in the light of the original post? There is no exact match for James' "method". There is a good explanation of the "a = b mod d" _congruence_relation_ (where the "=" actually has three bars), starting with section 4.6 on page 123. By the time we get to equation 4.37 on page 125, the discussion of the "conspicuous absence" of division is dealt with by defining the coprimality requirements, and addition, subtraction and by extension integral powers are esablished. James' work can then seen to be sloppy when you replace (as James defines) all his f_i variables (the factors) with k a_i, turning (f_1 + f_2 + f_3 + ... + f_m) into k (a_1 + a_2 + a_3 + ... + a_m) and (f_1 f_2 f_3 ... f_m) into k^m (a_1 a_2 a_3 ... a_m) Substitute these back into his equations (removing the f_i vars) and his equatons start to look rather silly. Be careful of division; thar be dragons if the coprime requirements aren't met. By the time you get to section 4.7 (as I read it), James' "discovery" proves that with m instances of the a_i vars, you can get any result you want, unless you can't (coprime requirements). Those coprime requirements are something that James would appear to have only a hint of an idea about, and he places few restrictions on the a_i vars (can they be rationals?) Equation 4.38 also gives a way out for solving division, but again there are requrements that james does not attempt to apply. I rambled a bit, but hope that helped at least a bit? M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist. |