Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: MichaelW on 7 Jun 2010 21:56 On Jun 8, 11:41 am, Ostap Bender <ostap_bender_1...(a)hotmail.com> wrote: > 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."- Hide quoted text - > > - Show quoted text - The next day he had one with cats where the cat did not even recognize its name (blah as well). I find Saturday Morning Breakfast Cereal is a modern equivalent (google smbc but somewhat nsfw).
From: JSH on 7 Jun 2010 22:35 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 Trivially proven. Turns out you can just consider m factors like f_1 = a_1*k mod N, multiply them together to get k^m = q mod N, or *add* them together to get my result, allowing you to trivially solve for k. So it's this trivial thing to show that factoring T = a_1*...a_m*q mod N, can give you k. Freaking easy little result, that is general as it works for m, a natural number. With m=1 a trivial case. > 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. REALLY? What if it's worse? Should it be forgotten as a nothing result in that case? What if it is freaking HORRIBLE, should it be lost to history for another 200 years or, maybe, just thankfully forgotten entirely by the human race? James Harris
From: MichaelW on 7 Jun 2010 23:14 On Mon, 07 Jun 2010 19:35:05 -0700, JSH wrote: > 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 > > Trivially proven. > > Turns out you can just consider m factors like f_1 = a_1*k mod N, > multiply them together to get k^m = q mod N, or *add* them together to > get my result, allowing you to trivially solve for k. > > So it's this trivial thing to show that factoring T = a_1*...a_m*q mod > N, can give you k. > > Freaking easy little result, that is general as it works for m, a > natural number. With m=1 a trivial case. > >> 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. > > REALLY? What if it's worse? > > Should it be forgotten as a nothing result in that case? > > What if it is freaking HORRIBLE, should it be lost to history for > another 200 years or, maybe, just thankfully forgotten entirely by the > human race? > > > James Harris James, welcome back. Just to remind you that this group is about the discussion of maths, not your cosmic significance. In order to be of maths interest a result ought to be... (1) an improvement on an existing technique (2) a tool that leads to further interesting results (3) elegant enough to be interesting in its own right (4) provide deeper insights into math truths I suggested an approach that might lead to (1) although to be honest by own kit bashing does not indicate much promise. To put things into perspective here is the Michael Residue Solver Algorithm. We have k^m = q mod N where m, q and N are given and we wish to solve for k. Let b = the length of the binary representation of N. Take the binary expansion of pi (fractional part) and take the first b bits as a number and test it as a solution k. If it fails take the next b bits and so on until you get a solution. For example let us solve k^3 = 8 mod 29. In this case b is 5 and (using this site http://www.befria.nu/elias/pi/binpi.html the first 5 bits of the fractional portion are 00100 = 4; nope. The next three potential k is 10000 = 16, nope again. The next is k is 11111 = 31 and 31^3 does indeed equal 8 mod 29! So here is my question: should my algorithm be forgotten by history or recorded forever? Regards, Michael W.
From: Tim Little on 8 Jun 2010 04:10 On 2010-06-08, MichaelW <msjmb(a)tpg.com.au> wrote: > We have k^m = q mod N where m, q and N are given and we wish to solve for > k. Let b = the length of the binary representation of N. > > Take the binary expansion of pi (fractional part) and take the first b > bits as a number and test it as a solution k. If it fails take the next b > bits and so on until you get a solution. [...] > So here is my question: should my algorithm be forgotten by history or > recorded forever? It should be recorded forever, next to such well-known algorithms as the BogoSort. - Tim
From: MichaelW on 8 Jun 2010 04:11
On Tue, 08 Jun 2010 08:10:28 +0000, Tim Little wrote: > On 2010-06-08, MichaelW <msjmb(a)tpg.com.au> wrote: >> We have k^m = q mod N where m, q and N are given and we wish to solve >> for k. Let b = the length of the binary representation of N. >> >> Take the binary expansion of pi (fractional part) and take the first b >> bits as a number and test it as a solution k. If it fails take the next >> b bits and so on until you get a solution. > [...] >> So here is my question: should my algorithm be forgotten by history or >> recorded forever? > > It should be recorded forever, next to such well-known algorithms as the > BogoSort. > > > - Tim To be fair the time for the MRSA to solve the equation is of the same order as sequentially checking 1,2,3... allowing that there is a theoretical possibility of taking infinite time. |