After my latest miss-steps I went back, looked everything over again
and finally noticed something that was bizarrely, simply obvious and
staring me in the face.
Here's the factoring algorithm that results.
Given an odd target composite T, for a test odd prime p, iterate
through non-zero integers k until
T - k^2 mod p
is a quadratic residue. If no k will work, discard that prime p and
try another. If one does work then get =E1 from
=E1^2 =3D (T - k^2)(k^2)^{-1} mod p.
Then you have residues of your factors modulo p from
f_1 =3D =E1k mod p
and
f_2 =3D =E1^{-1}(1 + =E1^2)k mod p
where f_1*f_2 =3D T.
Trivial factorizations if they are given can be discarded by noting
that your residues is the same as T, though one caveat is that for a
given prime p, one of your factors may equal the residue of the target
composite T.
Also if with r^2 =3D T - k^2 mod p, r^2 =3D k^2, then that result should
be discarded, though it may indicate that one of your factors equals
the residue of T for that particular prime.
The sign of the correct k and =E1 that work seems to correlate with the
sign of the factors as long as neither factor is less than p.
The simplification occurred to me after noticing a few obvious
things. It should work well though I guess maybe I'm still missing
something so out it goes to see if someone will test it.
If it does work well then factoring a target composite T is just about
getting enough primes that will work.
For example, if 80 primes are found then a target at least as large as
80! would topple even if you took primes starting at 3 and working
your way up, so assuming about 50% would work then using only primes
under 1000, you could factor a number greater than
7.1569457046263802294811533723187e+118.
James Harris
|
