Friday, January 18, 2008
JSH: Chasing solutions
The system of factoring congruences I found give two basic paths to getting a factorization with them, where I've debated which one is easier. Now at least I can describe them better:
Reiterating what the result is, with
z^2 = y^2 + nT
where T is the target to factor and n is some nonzero integer you pick, with p a prime you pick:
z = (2a)^{-1} (1 + 2a^2)k mod p,
k^2 = (a^2+1)^{-1}(nT) mod p
and
y = (1+2a^2)^{-1} z mod p
as I realized that the second solution I usually give is redundant.
The best case is with n=1, as then if p>sqrt(T), you only have the trivial factorization or the non-trivial one to switch between but that necessitates a search solving for k, where
k^2 = (a^2+1)^{-1}(T) mod p
and I intuitively feel that with increasing T, it will be harder and harder to find values for 'a' that will give quadratic residues modulo p. That just makes sense though classical thinking in this area would tell you that 50% of the a's would work. If so, then it's not an issue, and that would be the approach: set n=1 and check a's until you get a k.
One problem I have is determining if there is a quadratic residue found or not, as while I know there are well established tests, with my own algorithms I use only my own research. Luckily I have a fairly large body of number theory results—including a way to resolve quadratic residues—but I'm looking at efficiency here, and I don't have research that tells me when a number is a quadratic residue.
The other route then that I focused on, so that I didn't have to worry about any of that was to just pick some 'a' and then solve for n, which necessitated picking a k, but I intuitively feel that k must be very large, but I get to pick the quadratic residue I'll call q, where k^2 = q mod p, so
q = (a^2+1)^{-1}(nT) mod p
and I can solve for n in this case with n = q(a^2 + 1)T^{-1} mod p, but now I realize that n must be a minimum value as z-y mod p and z+y mod p are giving residues of factors modulo p of nT, so like, if I pick something very easy like q=4, then there is no real connection to T in the remaining equations for z and y.
But I don't have to figure out if something is a quadratic residue or not, as now I can just loop through quadratic residues and use the one with the smallest n, hoping I got it small enough.
So now finally I'm ready to write a program.
The problem I was facing was not really wanting to resolve quadratic residues, or having to determine if I had one, and this way gives me a way to not have to worry about that, but maybe that approach will usually give very large n's unless there is an exhaustive search.
Ok.
Oh, so do I have a solution to the factoring problem? I'd say, probably, yes. As there is still the other direct approach of using the Chinese Remainder theorem, where you can pick primes small enough that it's trivial to find a's that will work. I don't like that approach as, remember, I use my own research and I didn't discover the Chinese Remainder theorem, or I'd use it.
What I don't do, others can. Others might also just choose to loop through 'a' and resolve the quadratic residues.
Given that there are only two possibilities: the trivial or the non-trivial factorization, with n=1, there is no reasonable doubt that the equations solve the factoring problem.
The only objection left for the mathematical community, since I have mathematical proof, is that my lack of delivering a working algorithm is proof against mathematical proof.
And you people rest on that one for as long as you can, and I know what will happen: other people will do the other implementations and when they do, I'll point out that the mathematical community left the world unprotected and unwarned when a mathematical proof was right there, and it's so easy.
So I'll argue, waiting for me to deliver was just a dumb dodge in the hope that I couldn't figure out a way to implement something that plenty of other people around the world could, from desperate people who were so far gone that they would do ANYTHING to hold off facing the music for one more day.
Ok, so now I can program. And you people can wait.
Reiterating what the result is, with
z^2 = y^2 + nT
where T is the target to factor and n is some nonzero integer you pick, with p a prime you pick:
z = (2a)^{-1} (1 + 2a^2)k mod p,
k^2 = (a^2+1)^{-1}(nT) mod p
and
y = (1+2a^2)^{-1} z mod p
as I realized that the second solution I usually give is redundant.
The best case is with n=1, as then if p>sqrt(T), you only have the trivial factorization or the non-trivial one to switch between but that necessitates a search solving for k, where
k^2 = (a^2+1)^{-1}(T) mod p
and I intuitively feel that with increasing T, it will be harder and harder to find values for 'a' that will give quadratic residues modulo p. That just makes sense though classical thinking in this area would tell you that 50% of the a's would work. If so, then it's not an issue, and that would be the approach: set n=1 and check a's until you get a k.
One problem I have is determining if there is a quadratic residue found or not, as while I know there are well established tests, with my own algorithms I use only my own research. Luckily I have a fairly large body of number theory results—including a way to resolve quadratic residues—but I'm looking at efficiency here, and I don't have research that tells me when a number is a quadratic residue.
The other route then that I focused on, so that I didn't have to worry about any of that was to just pick some 'a' and then solve for n, which necessitated picking a k, but I intuitively feel that k must be very large, but I get to pick the quadratic residue I'll call q, where k^2 = q mod p, so
q = (a^2+1)^{-1}(nT) mod p
and I can solve for n in this case with n = q(a^2 + 1)T^{-1} mod p, but now I realize that n must be a minimum value as z-y mod p and z+y mod p are giving residues of factors modulo p of nT, so like, if I pick something very easy like q=4, then there is no real connection to T in the remaining equations for z and y.
But I don't have to figure out if something is a quadratic residue or not, as now I can just loop through quadratic residues and use the one with the smallest n, hoping I got it small enough.
So now finally I'm ready to write a program.
The problem I was facing was not really wanting to resolve quadratic residues, or having to determine if I had one, and this way gives me a way to not have to worry about that, but maybe that approach will usually give very large n's unless there is an exhaustive search.
Ok.
Oh, so do I have a solution to the factoring problem? I'd say, probably, yes. As there is still the other direct approach of using the Chinese Remainder theorem, where you can pick primes small enough that it's trivial to find a's that will work. I don't like that approach as, remember, I use my own research and I didn't discover the Chinese Remainder theorem, or I'd use it.
What I don't do, others can. Others might also just choose to loop through 'a' and resolve the quadratic residues.
Given that there are only two possibilities: the trivial or the non-trivial factorization, with n=1, there is no reasonable doubt that the equations solve the factoring problem.
The only objection left for the mathematical community, since I have mathematical proof, is that my lack of delivering a working algorithm is proof against mathematical proof.
And you people rest on that one for as long as you can, and I know what will happen: other people will do the other implementations and when they do, I'll point out that the mathematical community left the world unprotected and unwarned when a mathematical proof was right there, and it's so easy.
So I'll argue, waiting for me to deliver was just a dumb dodge in the hope that I couldn't figure out a way to implement something that plenty of other people around the world could, from desperate people who were so far gone that they would do ANYTHING to hold off facing the music for one more day.
Ok, so now I can program. And you people can wait.
# posted by James Harris @ 00:02 
