### Saturday, June 05, 2010

## Solving k^m = q mod N

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.

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.