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 23:42 On 2010-06-10, JSH <jstevh(a)gmail.com> wrote: > Actually an interesting program. You might want to do some research > with it and write a paper. Actually it is not at all an interesting program, except as a warning example of how even very poor methods for solving equations can still actually work. > But you don't want to test my ability to throw large examples at > you. Indeed, my program will start getting very slow for N > 1 000 000. It will still eventually work at least up to N = 2^31 though, as the presence of every sequence of length 31 (and actually greater) has been verified to exist within pi's binary expansion. > 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 tim(a)perth:~$ java TryPi 2 4096 4100 Found k = 2114 at bits 14976-14988 of pi 2114^2 = 4096 mod 4100 Have you tried any more general values of m and q yet, those other than m=2 and q=2^j? For example, try this arbitrarily chosen example: k^93 = 309 mod 498. Can your program solve that? Mine can: tim(a)perth:~$ java TryPi 93 309 498 Found k = 477 at bits 3528-3536 of pi 477^93 = 309 mod 498 Or is your program incapable? - Tim
From: JSH on 11 Jun 2010 00:09 On Jun 10, 8:42 pm, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-10, JSH <jst...(a)gmail.com> wrote: > > > Actually an interesting program. You might want to do some research > > with it and write a paper. > > Actually it is not at all an interesting program, except as a warning > example of how even very poor methods for solving equations can still > actually work. To you maybe, but does it exit in a way that indicates randomness in the pi sequence, or not? For instance you could do a series of low values for k, and see if it exited with 1/N probability or less, or more. > > But you don't want to test my ability to throw large examples at > > you. > > Indeed, my program will start getting very slow for N > 1 000 000. It > will still eventually work at least up to N = 2^31 though, as the > presence of every sequence of length 31 (and actually greater) has > been verified to exist within pi's binary expansion. Yeah. Not surprising. > > 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 > > tim(a)perth:~$ java TryPi 2 4096 4100 > Found k = 2114 at bits 14976-14988 of pi > 2114^2 = 4096 mod 4100 > > Have you tried any more general values of m and q yet, those other > than m=2 and q=2^j? For example, try this arbitrarily chosen example: > k^93 = 309 mod 498. Can your program solve that? Mine can: It's called "quadres.java" for a reason. It does quadratic residues. > > tim(a)perth:~$ java TryPi 93 309 498 > Found k = 477 at bits 3528-3536 of pi > 477^93 = 309 mod 498 > > Or is your program incapable? Incapable. It does quadratic residues. I put up a quartic residue program that is even more of a hack as well, and one can trivially put up an mth residue calculator with a simple relation: k^m = q mod N, just let a_1 through a_m=1, then T = mq mod N, so you can factor mq + Nj, where j is an integer, to find the f's. Then k = (f_1+...f_2)*m^{-1} mod N, assuming m is coprime to N. So for your example, you can try T = 93(309)+498. Factor that for the f's, and see if it works. I get lazy on trying to find a bunch of f's and often will just use f_1 = T, and let the other f's equal 1. I'm not programming it myself though. Make of that what you will. Doesn't matter to me. James Harris
From: MichaelW on 11 Jun 2010 00:57 On Jun 11, 2:09 pm, JSH <jst...(a)gmail.com> wrote: > > Incapable. It does quadratic residues. I put up a quartic residue > program that is even more of a hack as well, and one can trivially put > up an mth residue calculator with a simple relation: > > k^m = q mod N, just let a_1 through a_m=1, then T = mq mod N, so you > can factor mq + Nj, where j is an integer, to find the f's. > > Then k = (f_1+...f_2)*m^{-1} mod N, assuming m is coprime to N. > > So for your example, you can try T = 93(309)+498. Factor that for the > f's, and see if it works. > > I get lazy on trying to find a bunch of f's and often will just use > f_1 = T, and let the other f's equal 1. > > I'm not programming it myself though. > > Make of that what you will. Doesn't matter to me. > > James Harris Setting the a's to 1 will not work in this case since the sum (93) is not co-prime to the N (498) since both are divisible by 3 which breaks the condition in your original post.
From: Tim Little on 11 Jun 2010 02:18 On 2010-06-11, JSH <jstevh(a)gmail.com> wrote: > To you maybe, but does it exit in a way that indicates randomness in > the pi sequence, or not? > > For instance you could do a series of low values for k, and see if it > exited with 1/N probability or less, or more. It is already well known that the first few billion digits of pi pass essentially all known statistical tests of uniform randomness. Also, the average number of tests before exiting should not be N, it should be more like P/C, where P is the smallest power of 2 greater than or equal to N, and C is the count of values of k in the range [0,P) that satisfy the equation. C is usually greater than 1. For example with any even m and any solution k, N-k is also a solution so that C >= 2 unless the only solution is exactly N/2. Since the range of test-values for k usually exceeds N, there is also the possibility of N+k and 2N-k being found. You should already have noticed that the solution my program found to k^2 = 169 mod 177 was not the k=13 that yours found. - Tim
From: JSH on 11 Jun 2010 09:58
On Jun 10, 11:18 pm, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-11, JSH <jst...(a)gmail.com> wrote: > > > To you maybe, but does it exit in a way that indicates randomness in > > the pi sequence, or not? > > > For instance you could do a series of low values for k, and see if it > > exited with 1/N probability or less, or more. > > It is already well known that the first few billion digits of pi pass > essentially all known statistical tests of uniform randomness. > > Also, the average number of tests before exiting should not be N, it > should be more like P/C, where P is the smallest power of 2 greater > than or equal to N, and C is the count of values of k in the range > [0,P) that satisfy the equation. > > C is usually greater than 1. For example with any even m and any > solution k, N-k is also a solution so that C >= 2 unless the only > solution is exactly N/2. Since the range of test-values for k usually > exceeds N, there is also the possibility of N+k and 2N-k being found. > > You should already have noticed that the solution my program found to > k^2 = 169 mod 177 was not the k=13 that yours found. > > - Tim Dude, I don't really read a lot of posts. I mostly skim them. Nuff said. ___JSH |