Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: JSH on 5 Jun 2010 13:16 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 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. 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 it MAY have been discovered back then, but been considered too trivial to write down...and then it became lost. But prior mathematicians didn't have a world using integer factorization as a way to secure flows of information and billions upon billions of dollars. To them integer factorization did not have the meaning it has to people today. I've put the result into a paper and sent to the Annals of Mathematics in Princeton, and got a verification of receipt the next day, but of course I don't know if they're actually looking at it, or I got a polite reply used for "cranks". I've made several contacts by email, including Granville, Ribet, and others whose names don't come to me right now typing this post. No replies. Nothing. I'm getting little to no feedback on this result. My math blog is showing no up-tick in hits related to it. The only measure of its impact so far is, yup, Google, where the title of my paper "Solving Residues" is coming up #1. So I'm desperate enough to come back to Usenet as, um, things aren't supposed to work this way. If integer factorization gets re-written we're on a path to that happening in the worst way, with every major world power possible learning about it occurring by an exploit. Desperate nations might be the first to find a result like this one. If the general result does lead to another number theory, and another way to factor, and who knows what else, then these people could rapidly gain traction in ways they currently cannot by their current military power or technological infrastructure. So you could be witnessing the end of the current world order from a bizarre path. It may be destined, but I hope not. As if that happens, the future you see will not be the United States the dominant country, with Europe a dominant force, but those countries potentially on the BOTTOM, in a technologically advanced future we can no more see today, than people a hundred years ago could see this one. Being a citizen of the United States and living here quite happily I'd REALLY not like that scenario. So I know, many of you see yourselves as unimportant. You see what happens in these discussions as of no account as the world doesn't account for it much. In my opinion the dregs of math society end up on Usenet as where else can they go? You are people who are comfortable with being nobodies being told that the fate of the world requires that you do something, though it's not clear what. The future will arrive no matter what you do, and if you are later in an upside down world, you unlike so many others who will get dragged along who had no choice, no input, and no way to do anything, will know that you, did. James Harris
From: hagman on 6 Jun 2010 06:14 On 5 Jun., 19:16, 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 > > 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. > > 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 it MAY have been discovered back then, but been considered too > trivial to write down...and then it became lost. > > But prior mathematicians didn't have a world using integer > factorization as a way to secure flows of information and billions > upon billions of dollars. To them integer factorization did not have > the meaning it has to people today. > > I've put the result into a paper and sent to the Annals of Mathematics > in Princeton, and got a verification of receipt the next day, but of > course I don't know if they're actually looking at it, or I got a > polite reply used for "cranks". > > I've made several contacts by email, including Granville, Ribet, and > others whose names don't come to me right now typing this post. > > No replies. > > Nothing. > > I'm getting little to no feedback on this result. My math blog is > showing no up-tick in hits related to it. > > The only measure of its impact so far is, yup, Google, where the title > of my paper "Solving Residues" is coming up #1. > > So I'm desperate enough to come back to Usenet as, um, things aren't > supposed to work this way. If integer factorization gets re-written > we're on a path to that happening in the worst way, with every major > world power possible learning about it occurring by an exploit. > > Desperate nations might be the first to find a result like this one. > If the general result does lead to another number theory, and another > way to factor, and who knows what else, then these people could > rapidly gain traction in ways they currently cannot by their current > military power or technological infrastructure. > > So you could be witnessing the end of the current world order from a > bizarre path. It may be destined, but I hope not. > > As if that happens, the future you see will not be the United States > the dominant country, with Europe a dominant force, but those > countries potentially on the BOTTOM, in a technologically advanced > future we can no more see today, than people a hundred years ago could > see this one. > > Being a citizen of the United States and living here quite happily I'd > REALLY not like that scenario. > > So I know, many of you see yourselves as unimportant. You see what > happens in these discussions as of no account as the world doesn't > account for it much. In my opinion the dregs of math society end up > on Usenet as where else can they go? > > You are people who are comfortable with being nobodies being told that > the fate of the world requires that you do something, though it's not > clear what. > > The future will arrive no matter what you do, and if you are later in > an upside down world, you unlike so many others who will get dragged > along who had no choice, no input, and no way to do anything, will > know that you, did. > > James Harris And what makes this method notably faster than simply triyng k=1,2, ..., N-1? Note that this brute force runs in O(N) time and O(1) space. How fast is your stuff? Could you demonstrate your idea with a trivial example like k^2349167 = 29166469829073 mod 5570560728995753? Or at least an even more trivial example like k^3 = 973 mod 1073? The latter should be doable by hand with your method
From: Mark Murray on 6 Jun 2010 06:21 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.
From: JSH on 6 Jun 2010 11:26 On Jun 6, 3:14 am, hagman <goo...(a)von-eitzen.de> wrote: > On 5 Jun., 19:16, 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 > > > 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. > > > 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 it MAY have been discovered back then, but been considered too > > trivial to write down...and then it became lost. > > > But prior mathematicians didn't have a world using integer > > factorization as a way to secure flows of information and billions > > upon billions of dollars. To them integer factorization did not have > > the meaning it has to people today. > > > I've put the result into a paper and sent to the Annals of Mathematics > > in Princeton, and got a verification of receipt the next day, but of > > course I don't know if they're actually looking at it, or I got a > > polite reply used for "cranks". > > > I've made several contacts by email, including Granville, Ribet, and > > others whose names don't come to me right now typing this post. > > > No replies. > > > Nothing. > > > I'm getting little to no feedback on this result. My math blog is > > showing no up-tick in hits related to it. > > > The only measure of its impact so far is, yup, Google, where the title > > of my paper "Solving Residues" is coming up #1. > > > So I'm desperate enough to come back to Usenet as, um, things aren't > > supposed to work this way. If integer factorization gets re-written > > we're on a path to that happening in the worst way, with every major > > world power possible learning about it occurring by an exploit. > > > Desperate nations might be the first to find a result like this one. > > If the general result does lead to another number theory, and another > > way to factor, and who knows what else, then these people could > > rapidly gain traction in ways they currently cannot by their current > > military power or technological infrastructure. > > > So you could be witnessing the end of the current world order from a > > bizarre path. It may be destined, but I hope not. > > > As if that happens, the future you see will not be the United States > > the dominant country, with Europe a dominant force, but those > > countries potentially on the BOTTOM, in a technologically advanced > > future we can no more see today, than people a hundred years ago could > > see this one. > > > Being a citizen of the United States and living here quite happily I'd > > REALLY not like that scenario. > > > So I know, many of you see yourselves as unimportant. You see what > > happens in these discussions as of no account as the world doesn't > > account for it much. In my opinion the dregs of math society end up > > on Usenet as where else can they go? > > > You are people who are comfortable with being nobodies being told that > > the fate of the world requires that you do something, though it's not > > clear what. > > > The future will arrive no matter what you do, and if you are later in > > an upside down world, you unlike so many others who will get dragged > > along who had no choice, no input, and no way to do anything, will > > know that you, did. > > > James Harris > > 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. > Or at least an even more trivial example like > k^3 = 973 mod 1073? > The latter should be doable by hand with your method 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 It's zipped at QuarticRes.zip and is a quick and dirty try and just putting something together to try and answer some questions. Readers though can already see the knee-jerk that is so frustrating about Usenet. Posters give these replies meant to make you jump through hoops for THEIR PLEASURE, without regard to mathematical realities. And they have no limits as 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 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. They have no limits because they know *they* don't matter. The poster is some loser who knows nothing HE says matters, so if I'm here in the muck with him by his reckoning, nothing I say matters either. Important people don't get in his range. He NOWS that from years of hard, harsh experience. But again, I've gone to the "right people" already. Sent a paper to the Annals at Princeton. Directly contacted mathematicians like Granville and Ribet, and lesser known mathematicians as well, as yes, I know I may be blocked by spam filters. But that's another reason for me to toss this thing out here and risk the Usenet reality of nothing posters who have nothing lives ripping on research because they can't believe anything important could come into their swamp. Here the real math society MAY NOT BE following its own rules, so here I am, with the people on the bottom. Get over that and ask yourselves for real: how is a simple result at this level possible? And what can *anyone* do if the pro's at the top of the heap make a committee decision to just kind of not notice it is discovered? James Harris
From: Mark Murray on 6 Jun 2010 12:48
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. How does that qualify as "doing quartics"? M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist. |