Saturday, May 31, 2008
JSH: Residues and factoring
I'm hoping to shorten the arguing phase with the remarkably simple solution to the factoring problem I've outlined in a previous post by pointing out a few things:
Given a target composite T, and
z^2 = y^2 + nT
where n is an integer chosen for z to have 3 as a factor—so if T mod 3 = 1 then n=5 will work—then z exists as
z = (f_1 + f_2)/2
when f_1*f_2 = nT, and of course you want integer factors.
The method I have then allows you to find z using a variable I call k, where
z = 3k/2
and k^2 = 2^{-1} (nT) modulo p
where p is an odd prime less than k as k is an even positive integer.
May seem complicated all in a rush like that but it's incredibly simple.
The technique boils down to getting the residue of z modulo an odd prime p, by using the help of a variable I call k, and it just so happens it's easy to do that, if you think of it, but I guess no one else did so the factoring problem was wrongly thought to be hard.
But you may wonder, how about multiple solutions for z?
Well, multiple k's would just have to have the same residue modulo p.
Ok, then you may ask, how do you pick p?
Answer is that you just try some odd prime less than the minimum k, where since
z = 3k/2, and z = (f_1 + f_2)/2
you can find the minimum possible k by assuming f_1 = f_2, which is the case of nT being a perfect square.
So you just try some odd prime p less than the minimum k, and see if it works such that k exists with
k^2 = 2^{-1} (nT) modulo p
and if it doesn't you just try another prime! And you know that 50% of the time a given prime p should work.
You may wonder, is there any doubt about the proof or any way to question whether it works?
Short answer is, no. It's trivial algebra. The big thing that happened here is the use of a massively powerful although simple idea.
It just so happened that there was this clever way to figure out the residue of z modulo chosen odd primes, where I call them helper primes as all they do is help you factor your target composite T.
They were always there, waiting to be used.
Sometimes in mathematics a solution can be about luck and looking for something simple.
If you think a problem is hard, sometimes you can make it so, while doing real mathematical research is about not assuming what is not proven.
Maybe the greatest lesson for many of you to learn in your mathematical careers.
Mathematical proof is what you rely on, not social things like how many mathematicians before you looked at a problem, as they could ALL have missed something simple.
Given a target composite T, and
z^2 = y^2 + nT
where n is an integer chosen for z to have 3 as a factor—so if T mod 3 = 1 then n=5 will work—then z exists as
z = (f_1 + f_2)/2
when f_1*f_2 = nT, and of course you want integer factors.
The method I have then allows you to find z using a variable I call k, where
z = 3k/2
and k^2 = 2^{-1} (nT) modulo p
where p is an odd prime less than k as k is an even positive integer.
May seem complicated all in a rush like that but it's incredibly simple.
The technique boils down to getting the residue of z modulo an odd prime p, by using the help of a variable I call k, and it just so happens it's easy to do that, if you think of it, but I guess no one else did so the factoring problem was wrongly thought to be hard.
But you may wonder, how about multiple solutions for z?
Well, multiple k's would just have to have the same residue modulo p.
Ok, then you may ask, how do you pick p?
Answer is that you just try some odd prime less than the minimum k, where since
z = 3k/2, and z = (f_1 + f_2)/2
you can find the minimum possible k by assuming f_1 = f_2, which is the case of nT being a perfect square.
So you just try some odd prime p less than the minimum k, and see if it works such that k exists with
k^2 = 2^{-1} (nT) modulo p
and if it doesn't you just try another prime! And you know that 50% of the time a given prime p should work.
You may wonder, is there any doubt about the proof or any way to question whether it works?
Short answer is, no. It's trivial algebra. The big thing that happened here is the use of a massively powerful although simple idea.
It just so happened that there was this clever way to figure out the residue of z modulo chosen odd primes, where I call them helper primes as all they do is help you factor your target composite T.
They were always there, waiting to be used.
Sometimes in mathematics a solution can be about luck and looking for something simple.
If you think a problem is hard, sometimes you can make it so, while doing real mathematical research is about not assuming what is not proven.
Maybe the greatest lesson for many of you to learn in your mathematical careers.
Mathematical proof is what you rely on, not social things like how many mathematicians before you looked at a problem, as they could ALL have missed something simple.
# posted by James Harris @ 12:31 
