Monday, January 07, 2008
JSH: Where things stand with factoring congruences
I have been posting a lot about some factoring congruences I discovered and I've posted a derivation and posted those congruences more than once, but since I'm puzzling over something with them, I won't post them again here.
Now I've noted that if I am correct those congruences probably end RSA encryption which seems dramatic, ok, it is dramatic, but the mathematical explanation is trivial.
You see if you have integers z and y, where
z^2 = y^2 + T
and T is the target composite you are trying to factor, then, of course, you can have a non-trivial factorization of T. Well, what the factoring congruences I discovered allow you to do (supposedly as I puzzle through a problem with them) is find z mod p and y mod p, where p is just some prime you get to pick out of the blue.
That might not seem like much, but get this, if p is greater than sqrt(T), then it turns out that the residue modulo p of the smaller factor of T is, of course, that factor itself!!!
And the residues of the factors modulo p are given by z-y and z+y.
So you end up factoring the target.
That is the mathematical basis for my claim that RSA encryption is endangered by this approach.
In response I've faced posters challenging me to factor an RSA number, but no mathematician who believes in mathematical proof would bother with such a challenge!
Why not? Because the argument above is trivially correct, so the only thing that really matters is whether or not the factoring congruences work! As if they do, then any real mathematician would know that they would work to factor any composite, so the size is irrelevant.
Now I ran into problems, sadly enough, with T=21 and p=17, so maybe they don't work!
But the derivation seems simple enough and is posted!!!
So what's wrong? Do the factoring congruences work, or did I screw up the derivation?
And note that is the only really mathematical question here, so challenges to factor merely show a naive lack of understanding of mathematical proof.
Um, people, that's why mathematical proof is such a powerful concept—if you believe in it.
Now I've noted that if I am correct those congruences probably end RSA encryption which seems dramatic, ok, it is dramatic, but the mathematical explanation is trivial.
You see if you have integers z and y, where
z^2 = y^2 + T
and T is the target composite you are trying to factor, then, of course, you can have a non-trivial factorization of T. Well, what the factoring congruences I discovered allow you to do (supposedly as I puzzle through a problem with them) is find z mod p and y mod p, where p is just some prime you get to pick out of the blue.
That might not seem like much, but get this, if p is greater than sqrt(T), then it turns out that the residue modulo p of the smaller factor of T is, of course, that factor itself!!!
And the residues of the factors modulo p are given by z-y and z+y.
So you end up factoring the target.
That is the mathematical basis for my claim that RSA encryption is endangered by this approach.
In response I've faced posters challenging me to factor an RSA number, but no mathematician who believes in mathematical proof would bother with such a challenge!
Why not? Because the argument above is trivially correct, so the only thing that really matters is whether or not the factoring congruences work! As if they do, then any real mathematician would know that they would work to factor any composite, so the size is irrelevant.
Now I ran into problems, sadly enough, with T=21 and p=17, so maybe they don't work!
But the derivation seems simple enough and is posted!!!
So what's wrong? Do the factoring congruences work, or did I screw up the derivation?
And note that is the only really mathematical question here, so challenges to factor merely show a naive lack of understanding of mathematical proof.
Um, people, that's why mathematical proof is such a powerful concept—if you believe in it.
# posted by James Harris @ 21:10 
