Monday, December 31, 2007
Fundamental factoring relations
Given
z^2 = y^2 + nT
where T is the target composite to be factored, n is some nonzero integer, and z and y are rational you can solve for z modulo any odd prime p coprime to 3, y, z and nT, with the following crucial congruences:
z = 2^{-1}(3k) mod p
and
k^2 = 2^{-1}(nT) mod p
And those are the fundamental factoring relations.
Those of you who are honest will, once you check and verify that they always work, as they do, that RSA encryption is over. But if you wish to lie to the world and deny that fact then I hope you are brave enough to handle the consequences that I now assure you will be there.
The reason this information makes RSA encryption obsolete is that you can just pick p to be some prime greater than sqrt(nT) and solve for y and z mod p, to solve for factors mod p, and get the smaller factor directly as a residue.
The necessity of shifting n if 2^{-1}(nT) mod p is not a quadratic residue should be fixable with more generalized equations.
Also, it seems to me that you can solve for y directly using -nT, as then you'd have
y^2 = z^2 + (-nT)
and why should the math care if you switch z out from those congruences with y? If so then you can use these congruences to solve for y and z without ever needing to solve a quadratic residue.
z^2 = y^2 + nT
where T is the target composite to be factored, n is some nonzero integer, and z and y are rational you can solve for z modulo any odd prime p coprime to 3, y, z and nT, with the following crucial congruences:
z = 2^{-1}(3k) mod p
and
k^2 = 2^{-1}(nT) mod p
And those are the fundamental factoring relations.
Those of you who are honest will, once you check and verify that they always work, as they do, that RSA encryption is over. But if you wish to lie to the world and deny that fact then I hope you are brave enough to handle the consequences that I now assure you will be there.
The reason this information makes RSA encryption obsolete is that you can just pick p to be some prime greater than sqrt(nT) and solve for y and z mod p, to solve for factors mod p, and get the smaller factor directly as a residue.
The necessity of shifting n if 2^{-1}(nT) mod p is not a quadratic residue should be fixable with more generalized equations.
Also, it seems to me that you can solve for y directly using -nT, as then you'd have
y^2 = z^2 + (-nT)
and why should the math care if you switch z out from those congruences with y? If so then you can use these congruences to solve for y and z without ever needing to solve a quadratic residue.
# posted by James Harris @ 01:51 
