Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: Tim Little on 10 Jun 2010 02:25 On 2010-06-10, MichaelW <msjmb(a)tpg.com.au> wrote: > I can't decide if that is awesome or weird. Or both. Heh, that's why I actually went to the trouble of writing it. In practice my implementation's running time is dominated by generating digits of pi. I did not use anything like the fastest algorithm. > Does there exist a binary string of some length that never appears > in the binary expansion of pi? If such a string exists then the > algorithm fails. Yes. Despite this, I implemented it with the certainty that it will work for any example that James' program can handle. - Tim
From: JSH on 10 Jun 2010 10:24 On Jun 9, 11:25 pm, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-10, MichaelW <ms...(a)tpg.com.au> wrote: > > > I can't decide if that is awesome or weird. Or both. > > Heh, that's why I actually went to the trouble of writing it. In > practice my implementation's running time is dominated by generating > digits of pi. I did not use anything like the fastest algorithm. > > > Does there exist a binary string of some length that never appears > > in the binary expansion of pi? If such a string exists then the > > algorithm fails. > > Yes. Despite this, I implemented it with the certainty that it will > work for any example that James' program can handle. > > - Tim Actually an interesting program. You might want to do some research with it and write a paper. But you don't want to test my ability to throw large examples at you. Here's another from my program. I think that with 2^j I can go as high as necessary to break your machine with my method handling it trivially. java QuadRes 4096 4100 k=64 64^2 = 4096 mod 4100 a_1=1, a_2=2 f_1=64, f_2=128 T = 8192 8192 mod 4100 = 4092 Total number of T's used: 1 Total number of factorizations: 6 (Oh, had to add back in carriage returns. Can SOMEONE tell Google to freaking fix Chrome so that when I copy and paste from newsgroups it doesn't lose freaking carriage returns? Firefox doesn't have that problem.) And I'll remind that general results in mathematics quite simply can do who knows what. That's why they're general results. It is interesting though seeing posters persist in trying to dismiss a foundation level result. Think of it this way, foundation results are at the START of the math textbook. Everything else builds on them. Historians and psychologists may find the behavior of interest though. James Harris
From: MichaelW on 10 Jun 2010 17:32 On Jun 11, 12:24 am, JSH <jst...(a)gmail.com> wrote: > Actually an interesting program. You might want to do some research > with it and write a paper. > > But you don't want to test my ability to throw large examples at you. > Sure we do! When doing research only a fool take failure personally; a failure is just another kind of data point. > Here's another from my program. I think that with 2^j I can go as > high as necessary to break your machine with my method handling it > trivially. > > java QuadRes 4096 4100 > > k=64 > > 64^2 = 4096 mod 4100 > > a_1=1, a_2=2 > > f_1=64, f_2=128 > > T = 8192 > > 8192 mod 4100 = 4092 > > Total number of T's used: 1 > Total number of factorizations: 6 Yes, for your algorithm if the solution is of the form k=2^j and k^2 is less than N then you will take j factorizations. For my algorithm the expected number of bit patterns checked would be roughly equal to N. > > (Oh, had to add back in carriage returns. Can SOMEONE tell Google to > freaking fix Chrome so that when I copy and paste from newsgroups it > doesn't lose freaking carriage returns? Firefox doesn't have that > problem.) > > And I'll remind that general results in mathematics quite simply can > do who knows what. > > That's why they're general results. > > It is interesting though seeing posters persist in trying to dismiss a > foundation level result. > > Think of it this way, foundation results are at the START of the math > textbook. Everything else builds on them. > > Historians and psychologists may find the behavior of interest though. > > James Harris Another word for foundation result is the basics. If all you can do is the basics and not the advanced stuff then you are agreeing with a point that myself and others have made; compared to the academics you so despise you are simply out of your league. Regards, Michael W.
From: JSH on 10 Jun 2010 19:55 On Jun 10, 2:32 pm, MichaelW <ms...(a)tpg.com.au> wrote: > On Jun 11, 12:24 am, JSH <jst...(a)gmail.com> wrote: > > > Actually an interesting program. You might want to do some research > > with it and write a paper. > > > But you don't want to test my ability to throw large examples at you. > > Sure we do! When doing research only a fool take failure personally; a > failure is just another kind of data point. > > > > > > > Here's another from my program. I think that with 2^j I can go as > > high as necessary to break your machine with my method handling it > > trivially. > > > java QuadRes 4096 4100 > > > k=64 > > > 64^2 = 4096 mod 4100 > > > a_1=1, a_2=2 > > > f_1=64, f_2=128 > > > T = 8192 > > > 8192 mod 4100 = 4092 > > > Total number of T's used: 1 > > Total number of factorizations: 6 > > Yes, for your algorithm if the solution is of the form k=2^j and k^2 > is less than N then you will take j factorizations. For my algorithm You're guessing. Here's output with a smaller value: java QuadRes 1024 1033 k=32 32^2 = 1024 mod 1033 a_1=1, a_2=2 f_1=32, f_2=64 T = 2048 2048 mod 1033 = 1015 Total number of T's used: 3 Total number of factorizations: 13 > the expected number of bit patterns checked would be roughly equal to > N. That is, you assume your idea is random. But then you're assuming that the digits of pi are random as well. And again, you're clearly NOT a mathematician! Any other math people wish to assume that the digits of pi are random and that the poster's algorithm will exit as he expects? Can *anyone* even prove that it will always exit? I would think that's provable. But I doubt it's trivial to prove when it's most likely to exit. So again, I think it could be an interesting paper for "Tim Little" who already has written a program so he might as well do some experiments with it and write it up as a paper. > > > > > > > (Oh, had to add back in carriage returns. Can SOMEONE tell Google to > > freaking fix Chrome so that when I copy and paste from newsgroups it > > doesn't lose freaking carriage returns? Firefox doesn't have that > > problem.) > > > And I'll remind that general results in mathematics quite simply can > > do who knows what. > > > That's why they're general results. > > > It is interesting though seeing posters persist in trying to dismiss a > > foundation level result. > > > Think of it this way, foundation results are at the START of the math > > textbook. Everything else builds on them. > > > Historians and psychologists may find the behavior of interest though. > > > James Harris > > Another word for foundation result is the basics. If all you can do is > the basics and not the advanced stuff then you are agreeing with a > point that myself and others have made; compared to the academics you > so despise you are simply out of your league. > > Regards, Michael W. I'm not a mathematician. I'm not playing in their league at all. James Harris
From: MichaelW on 10 Jun 2010 21:47
On Jun 11, 9:55 am, JSH <jst...(a)gmail.com> wrote: > On Jun 10, 2:32 pm, MichaelW <ms...(a)tpg.com.au> wrote: > > > > > > > On Jun 11, 12:24 am, JSH <jst...(a)gmail.com> wrote: > > > > Actually an interesting program. You might want to do some research > > > with it and write a paper. > > > > But you don't want to test my ability to throw large examples at you. > > > Sure we do! When doing research only a fool take failure personally; a > > failure is just another kind of data point. > > > > Here's another from my program. I think that with 2^j I can go as > > > high as necessary to break your machine with my method handling it > > > trivially. > > > > java QuadRes 4096 4100 > > > > k=64 > > > > 64^2 = 4096 mod 4100 > > > > a_1=1, a_2=2 > > > > f_1=64, f_2=128 > > > > T = 8192 > > > > 8192 mod 4100 = 4092 > > > > Total number of T's used: 1 > > > Total number of factorizations: 6 > > > Yes, for your algorithm if the solution is of the form k=2^j and k^2 > > is less than N then you will take j factorizations. For my algorithm > > You're guessing. > > Here's output with a smaller value: > > java QuadRes 1024 1033 > > k=32 > > 32^2 = 1024 mod 1033 > > a_1=1, a_2=2 > > f_1=32, f_2=64 > > T = 2048 > > 2048 mod 1033 = 1015 > > Total number of T's used: 3 > Total number of factorizations: 13 > > > the expected number of bit patterns checked would be roughly equal to > > N. > > That is, you assume your idea is random. But then you're assuming > that the digits of pi are random as well. > > And again, you're clearly NOT a mathematician! > > Any other math people wish to assume that the digits of pi are random > and that the poster's algorithm will exit as he expects? > > Can *anyone* even prove that it will always exit? > > I would think that's provable. But I doubt it's trivial to prove when > it's most likely to exit. > > So again, I think it could be an interesting paper for "Tim Little" > who already has written a program so he might as well do some > experiments with it and write it up as a paper. > > > > > > > > > > (Oh, had to add back in carriage returns. Can SOMEONE tell Google to > > > freaking fix Chrome so that when I copy and paste from newsgroups it > > > doesn't lose freaking carriage returns? Firefox doesn't have that > > > problem.) > > > > And I'll remind that general results in mathematics quite simply can > > > do who knows what. > > > > That's why they're general results. > > > > It is interesting though seeing posters persist in trying to dismiss a > > > foundation level result. > > > > Think of it this way, foundation results are at the START of the math > > > textbook. Everything else builds on them. > > > > Historians and psychologists may find the behavior of interest though.. > > > > James Harris > > > Another word for foundation result is the basics. If all you can do is > > the basics and not the advanced stuff then you are agreeing with a > > point that myself and others have made; compared to the academics you > > so despise you are simply out of your league. > > > Regards, Michael W. > > I'm not a mathematician. I'm not playing in their league at all. > > James Harris- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text - Regarding the randomness of pi see here: http://www.nersc.gov/~dhbailey/dhbpapers/baicran.pdf This is a 16 page paper that addresses the questions raised for pi and other irrationals (in hexadecimal in this case). Short summary: almost certainly but not rigorously proven. I have deliberately avoided defining the term "random" and in truth for my purposes it is a poor term to use. Better would be to say that any binary string is equally likely to occur as any other binary string within the expansion of pi; this is the approach taken in the paper. In any case the point of my algorithm was to provide a benchmark. If your algorithm is indeed superior to pseudo-random guessing then it should *on average over all possible values of q* return a value for k in quicker time. Note that individual cases are not indicative (although interesting in their own right). We need to get the overall average. From my own research I am consider that counting through from 1 to N/2 would give an average of N/4 attempts (approximate sum of 1...N/2 divided by N/2). Any other ordering mechanism such as the pi algorithm would give a similar result. Your algorithm requires N/12 attempts on average, a significant improvement. This is what I have been trying to get you to look at. If you spent as much energy on the maths as you do on treating everyone as your personal enemy you might actually achieve something. Regards, Michael W. |