Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: MichaelW on 7 Jun 2010 19:27 On Jun 8, 8:15 am, Mark Murray <w.h.o...(a)example.com> wrote: > 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. Mark, Most helpful, thankyou. So is it fairer to say that the sections you refer to operate as a critique of his approach (indirectly) rather than an example of his approach? I ask this because what James is asking is <quote> 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? </quote> Now his is of course confusing novelty with value but to be fair it would appear that his exact approach does not appear anywhere else. Regards, Michael W.
From: JSH on 7 Jun 2010 19:57 On Jun 7, 4:27 pm, MichaelW <ms...(a)tpg.com.au> wrote: > On Jun 8, 8:15 am, Mark Murray <w.h.o...(a)example.com> wrote: > > > > > > > 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. > > Mark, > > Most helpful, thankyou. So is it fairer to say that the sections you > refer to operate as a critique of his approach (indirectly) rather > than an example of his approach? I ask this because what James is > asking is > > <quote> > 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? > </quote> > > Now his is of course confusing novelty with value but to be fair it > would appear that his exact approach does not appear anywhere else. > > Regards, Michael W. Thanks dude! Maybe I HAVE been too mean to you in the past. But at least I was certain in those cases that you were deliberately trying to block me in various ways. But hey perceptions can be wrong, I admit that I can see blocking where others might see objective critiques. Here the backstory is actually kind of interesting, as I finally realized that a surrogate factoring idea I was certain was great, um, couldn't work well. Luckily before I finally accepted that I'd already reversed the surrogate factoring equations, and found this weird relation for solving for a quadratic residue. I kind of puzzled over that for months and didn't think much of it until I generalized it November 2009. I then wandered off for a few more months until recently I started talking about it again, and then realized I could generalize again to k^m = q mod N. So the other side of my arguing things out is that it can take years for me to get to an answer, and even months when it's almost staring right at me! Fun, fun, fun! So weird though... It's too bad that discussions so often end up being insult-fests, but I do give my process upfront. Lots of ideas, toss them out there, argue about them, pondering them over time and if something sticks, run with it. If not TOSS it! I call it extreme mathematics. Many seem to hate it though. But I love it. James Harris
From: JSH on 7 Jun 2010 20:23 On Jun 5, 10:16 am, JSH <jst...(a)gmail.com> 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. > > Here's the full result and simple derivation: > > 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 Reminder that here is the result. > 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. > > So what I found is a simple general result of modular arithmetic. So the world now has a way to approach solving for k, when k^m = q mod N, when m is a natural number, by factoring, which is fully generalized in that it also works trivially for m=1. That is, it seems, a world first. > But supposedly such results were all found long ago. This result by > current mathematical teaching, should not exist as a new result. It > should have been discovered nearly 200 years ago, around the time that > Gauss introduced modular arithmetic. And yes the result is simple. But look at your math textbooks, a lot of the early results look trivial to modern eyes. But someone discovered each one of them, and they got written down. All the simple results were supposedly discovered already. Maybe this one was missed. But also this result may have been known to Gauss, but he was notorious for not telling everything he discovered. In this case he may have changed human history in a rather big way. Or he may have written it down and no one noticed. German scholars are better for checking on that possibility. The problem is that in mathematics, simple general results are usually profound. Profound as in massive impact. This one could re-write the textbooks on integer factorization. Humanity may not know integer factorization, yet, because it didn't have a simple important result before now. Don't let Usenet posters confuse you here and remember, as the discoverer if that holds, I have my place in the history books on this alone, regardless of my prior claims. That kind of thing sparks jealous and angry reactions especially maybe from people who have despised me for years and felt quite free to say so in posts!!! Big math names have been notified. Major journal has a paper on it. Now I'm talking it out here just in case and because, hey, if you had a result like this one, wouldn't you want to talk about it? I'm a historical figure, get over it. James Harris
From: MichaelW on 7 Jun 2010 21:31 On Jun 8, 10:23 am, JSH <jst...(a)gmail.com> wrote: > On Jun 5, 10:16 am, JSH <jst...(a)gmail.com> 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. > > > Here's the full result and simple derivation: > > > 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 > > Reminder that here is the result. > > > 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. > > > So what I found is a simple general result of modular arithmetic. > > So the world now has a way to approach solving for k, when k^m = q mod > N, when m is a natural number, by factoring, which is fully > generalized in that it also works trivially for m=1. > > That is, it seems, a world first. > > > But supposedly such results were all found long ago. This result by > > current mathematical teaching, should not exist as a new result. It > > should have been discovered nearly 200 years ago, around the time that > > Gauss introduced modular arithmetic. > > And yes the result is simple. But look at your math textbooks, a lot > of the early results look trivial to modern eyes. But someone > discovered each one of them, and they got written down. > > All the simple results were supposedly discovered already. Maybe this > one was missed. > > But also this result may have been known to Gauss, but he was > notorious for not telling everything he discovered. In this case he > may have changed human history in a rather big way. > > Or he may have written it down and no one noticed. German scholars > are better for checking on that possibility. > > The problem is that in mathematics, simple general results are usually > profound. Profound as in massive impact. This one could re-write the > textbooks on integer factorization. > > Humanity may not know integer factorization, yet, because it didn't > have a simple important result before now. > > Don't let Usenet posters confuse you here and remember, as the > discoverer if that holds, I have my place in the history books on this > alone, regardless of my prior claims. > > That kind of thing sparks jealous and angry reactions especially maybe > from people who have despised me for years and felt quite free to say > so in posts!!! > > Big math names have been notified. Major journal has a paper on it. > Now I'm talking it out here just in case and because, hey, if you had > a result like this one, wouldn't you want to talk about it? > > I'm a historical figure, get over it. > > James Harris James, At the moment I am assuming that you are claiming a general methodology for solving k^m = q mod N Taking a simple case consider m=3 and N = a prime such that N+1 is divisible by 3. It is fairly easy to show for every q in {0,1,2....N-1} there is a single solution k in the same range. However there is no good algorithm as far as I know for actually solving apart from brute force. That is, take each possible value of k, cube it (two multiplications) and get the residue mod N (one division) and see if it matches q. This approach takes 3 multiplications/divisions for each value of k and we may have to test up to q possible values so let us say it takes 3*q significant operations (ignoring addition and subtraction) to find a solution. Let us now consider your algorithm. At each iteration we arbitarily select any triplet (a_1, a_2, a_3). Set T= q * a_1 * a_2 * a_3 (3 multiplications) Now arbitarily select T' such that T' = T mod N (this can be done with addition/subtraction so we won't add to the count) Determine three factors of T such that f_1 * f_2 * f_3 = T (at least one division; let's be generous and call it one) Calculate (a_1 + a_2 + a_3)^-1 mod N This is tricky. You can do it in your code by using the Java maths function "gcd" but this masks the number of iterations it takes. In Excel I use the follow brute force approach: =MATCH(1,INDEX(MOD(ROW(INDIRECT("1:"&A2))*E2,A2),0 ),0) where A2 contains N and E2 contains the sum of the a's. Strictly speaking the number of calculations depends upon the size of N but let's call it 6 operations (it is typically much more). Check out this site http://2000clicks.com/MathHelp/NumberChineseExtendedEuclideanAlgorithm.aspx and note that each *line* in the table that calculates the result represents two multiplications and a division. Now we can find k = sum of the f's divided by the sum of the a's mod N (two operations). So for each T we choose to factor it costs at least 9 operations plus the three to generate the T. To be historically significant therefore your brute force algorithm needs to be at least three times as likely to find a solution as the more obviously brute force algorithm of working through the possible values of k. I would suggest that the easiest way to do this is to generalise your code to determine the search times for all values for some large N and print the average. Regards, Michael W.
From: Ostap Bender on 7 Jun 2010 21:41
On Jun 7, 6:31 pm, MichaelW <ms...(a)tpg.com.au> wrote: > On Jun 8, 10:23 am, JSH <jst...(a)gmail.com> wrote: > > > > > On Jun 5, 10:16 am, JSH <jst...(a)gmail.com> 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. > > > > Here's the full result and simple derivation: > > > > 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 > > > Reminder that here is the result. > > > > 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. > > > > So what I found is a simple general result of modular arithmetic. > > > So the world now has a way to approach solving for k, when k^m = q mod > > N, when m is a natural number, by factoring, which is fully > > generalized in that it also works trivially for m=1. > > > That is, it seems, a world first. > > > > But supposedly such results were all found long ago. This result by > > > current mathematical teaching, should not exist as a new result. It > > > should have been discovered nearly 200 years ago, around the time that > > > Gauss introduced modular arithmetic. > > > And yes the result is simple. But look at your math textbooks, a lot > > of the early results look trivial to modern eyes. But someone > > discovered each one of them, and they got written down. > > > All the simple results were supposedly discovered already. Maybe this > > one was missed. > > > But also this result may have been known to Gauss, but he was > > notorious for not telling everything he discovered. In this case he > > may have changed human history in a rather big way. > > > Or he may have written it down and no one noticed. German scholars > > are better for checking on that possibility. > > > The problem is that in mathematics, simple general results are usually > > profound. Profound as in massive impact. This one could re-write the > > textbooks on integer factorization. > > > Humanity may not know integer factorization, yet, because it didn't > > have a simple important result before now. > > > Don't let Usenet posters confuse you here and remember, as the > > discoverer if that holds, I have my place in the history books on this > > alone, regardless of my prior claims. > > > That kind of thing sparks jealous and angry reactions especially maybe > > from people who have despised me for years and felt quite free to say > > so in posts!!! > > > Big math names have been notified. Major journal has a paper on it. > > Now I'm talking it out here just in case and because, hey, if you had > > a result like this one, wouldn't you want to talk about it? > > > I'm a historical figure, get over it. > > > James Harris > > James, > > At the moment I am assuming that you are claiming a general > methodology for solving > > k^m = q mod N > > Taking a simple case consider m=3 and N = a prime such that N+1 is > divisible by 3. It is fairly easy to show for every q in > {0,1,2....N-1} there is a single solution k in the same range. However > there is no good algorithm as far as I know for actually solving apart > from brute force. That is, take each possible value of k, cube it (two > multiplications) and get the residue mod N (one division) and see if > it matches q. > > This approach takes 3 multiplications/divisions for each value of k > and we may have to test up to q possible values so let us say it takes > 3*q significant operations (ignoring addition and subtraction) to find > a solution. > > Let us now consider your algorithm. At each iteration we arbitarily > select any triplet (a_1, a_2, a_3). > > Set T= q * a_1 * a_2 * a_3 (3 multiplications) > > Now arbitarily select T' such that T' = T mod N (this can be done > with addition/subtraction so we won't add to the count) > > Determine three factors of T such that f_1 * f_2 * f_3 = T (at > least one division; let's be generous and call it one) > > Calculate (a_1 + a_2 + a_3)^-1 mod N > > This is tricky. You can do it in your code by using the Java maths > function "gcd" but this masks the number of iterations it takes. In > Excel I use the follow brute force approach: > > =MATCH(1,INDEX(MOD(ROW(INDIRECT("1:"&A2))*E2,A2),0 ),0) > > where A2 contains N and E2 contains the sum of the a's. Strictly > speaking the number of calculations depends upon the size of N but > let's call it 6 operations (it is typically much more). Check out this > site > > http://2000clicks.com/MathHelp/NumberChineseExtendedEuclideanAlgorith... > > and note that each *line* in the table that calculates the result > represents two multiplications and a division. > > Now we can find k = sum of the f's divided by the sum of the a's mod N > (two operations). > > So for each T we choose to factor it costs at least 9 operations plus > the three to generate the T. > > To be historically significant therefore your brute force algorithm > needs to be at least three times as likely to find a solution as the > more obviously brute force algorithm of working through the possible > values of k. > > I would suggest that the easiest way to do this is to generalise your > code to determine the search times for all values for some large N and > print the average. > > Regards, Michael W. The thought of JSH reading your post reminds me of an old Gary Larson's Far Side cartoon: http://answers.google.com/answers/threadview/id/416754.html There is a Gary Larson "Far Side" cartoon that has two panels. The first panel is titled "What we say to dogs." A man is scolding his dog. The man's word-balloon says this: "Okay, Ginger! I've had it! You stay out of the garbage! Understand, Ginger? Stay out of the garbage, or else!?" The second panel is titled "What they hear." The drawing is exactly like the first panel, but this time the man's word-balloon says "Blah blah GINGER blah blah blah blah blah blah blah blah GINGER blah blah blah blah blah." |