## Factoring 12 digit numbers.

Expand Messages
• I applied one of the principles of the quadratic sieve ( without using the sieve part ) to extend the Fermat difference of squares method to factor larger
Message 1 of 1 , Jan 31, 2008
I applied one of the principles of the quadratic sieve ( without using
the sieve part )
to extend the Fermat difference of squares method to factor larger
numbers more quickly than
would the usual Fermat method.

Here is an example number that would not have easily been factored by
trial division.

Probably it would also yield quickly to other well known algorithms, but
I've not tested that.

My algorithm is a strictly deterministic algorithm.

Let r = int(sqrt(z))

We search for t such that t squared = s squared with t not equal to s or
-s mod z.

Start at t = r + 1.

Calculate in mod z, t**2, t**4, t**8, t**16, etc until the exponent is
largest power of 2 < z,
or until an integer square is found, or until the series begins to repeat.

If no integer square is found then multiply the non-squares two at a
time to search for a square product.

If not successful, multiply the non-squares three at a time to search
for a square product.

If not successful, multiply the non-squares four at a time to search for
a square product.

>>> ExtendedFermat(products12[1])

Factoring 519240287353L
>>>

Found Factors by four way product of power squares. steps = 2350 r
= 720583 t = 720586 t - r = 3
[800231L, 648863L]
>>>

Kermit Rose < kermit@... >
Your message has been successfully submitted and would be delivered to recipients shortly.