Saturday, March 28, 2009
JSH: Too simple factoring idea, quadratic residues
I've been playing around with Pell's Equation still but off and on still thinking about factoring after my MASSIVE failure with my general solution to Pell's Equation which didn't factor like I really, really, wanted it to, and I realized something simple:
Given a target composite T, and an integer m, such that m^2 > T:
with m^2 - T = r,
the residue r must be a quadratic residue modulo EACH prime factor of T, which is just so trivial that I know this quick factoring idea must be known, but here goes anyway.
Well each prime has (p-1)/2 quadratic residues, so the probability that two primes have exactly the same non-square r as a quadratic residue is roughly, 50%. So there is roughly a 50% chance that they do not. I say they bump each other.
So then what? Well the math has no choice but to give them a shared perfect square residue—as both DO have that one—and then you can factor.
For example, T = 35 = 5(7). Note that 36 - 35 = 1, and 6+1 = 7, and 6 - 1 = 5.
The two primes bump because 5 has no non-square quadratic residues in common with 7, so the math is forced to use a perfect square.
Here's an example where two factors do share one: T = 7(17) = 119, as they both have 2 as a non-square quadratic residue, and yup, 121 - 119 = 2, as the math uses that shared one and there isn't any prime fighting going on.
But hey, what are the odds of THREE primes all in agreement? Let's try tossing in 3, and I have:
19^2 - 3(5)(7) = 4
so yeah, they bumped into each other!
And notice (19 - 2) = 17, and (19+2) = 21, and I pulled out a non-trivial factorization by playing probabilities.
(Ok, I know that one is weird as 3 doesn't have ANY non-square residues!!! So what gives?)
Playing around with this idea a bit I noticed you seem to need a prime smaller than the prime factors of the target, or maybe this example is just a random case, as, um, I've only done one.
But it is kind of cool, and very obvious: non-square quadratic residues dominate, especially with bigger primes, and the probability of two primes having the same one is about 50%.
I DO assume that the RSA people check for this possibility?
If not you can factor an RSA public key with it, about 50% of the time.
Given a target composite T, and an integer m, such that m^2 > T:
with m^2 - T = r,
the residue r must be a quadratic residue modulo EACH prime factor of T, which is just so trivial that I know this quick factoring idea must be known, but here goes anyway.
Well each prime has (p-1)/2 quadratic residues, so the probability that two primes have exactly the same non-square r as a quadratic residue is roughly, 50%. So there is roughly a 50% chance that they do not. I say they bump each other.
So then what? Well the math has no choice but to give them a shared perfect square residue—as both DO have that one—and then you can factor.
For example, T = 35 = 5(7). Note that 36 - 35 = 1, and 6+1 = 7, and 6 - 1 = 5.
The two primes bump because 5 has no non-square quadratic residues in common with 7, so the math is forced to use a perfect square.
Here's an example where two factors do share one: T = 7(17) = 119, as they both have 2 as a non-square quadratic residue, and yup, 121 - 119 = 2, as the math uses that shared one and there isn't any prime fighting going on.
But hey, what are the odds of THREE primes all in agreement? Let's try tossing in 3, and I have:
19^2 - 3(5)(7) = 4
so yeah, they bumped into each other!
And notice (19 - 2) = 17, and (19+2) = 21, and I pulled out a non-trivial factorization by playing probabilities.
(Ok, I know that one is weird as 3 doesn't have ANY non-square residues!!! So what gives?)
Playing around with this idea a bit I noticed you seem to need a prime smaller than the prime factors of the target, or maybe this example is just a random case, as, um, I've only done one.
But it is kind of cool, and very obvious: non-square quadratic residues dominate, especially with bigger primes, and the probability of two primes having the same one is about 50%.
I DO assume that the RSA people check for this possibility?
If not you can factor an RSA public key with it, about 50% of the time.
# posted by James Harris @ 00:03 
