I'm comparing the time of three different algorithms.

FactorBrent is the polynomial recursion algorithm

x = x**2 + 1 mod z

Factor T is my variation of the Fermat difference of squares algorithm.

Factor Fermat is the classical Fermat difference of squares algorithm.

I find it interesting that comparison of these two examples suggest that

if the two factors are sufficiently close together, then the classic

Fermat difference of squares

algorithm is faster than my variation.

If the two factors are far apart, then my variation seems to be the

faster of the two.

Of course the Brent polynomial recursion algorithm is much much faster

than either of the others.

z = 5673678604496447 = 70907371L * 80015357L

Time taken to factor by

FactorBrent: 0.483999967575 seconds.

FactorT: 15.7090001106 seconds.

FactorFermat: 6.20899987221 seconds.

z = 1233711939594151 = 16870433L * 73128647L

Time taken to factor by

FactorBrent: 0.483000040054 seconds.

FactorT: 41.9019999504 seconds.

FactorFermat: 490.794999838 seconds.

My variation of the Fermat difference of squares is that

instead of locating the potential t values in

t**2 - s**2 = z, by repetitively adding 2,

I generate the t values by Chinese remainder theorem

applied to

the solutions for t mod 3, t mod 5, t mod 7, etc, until the correct

value for t is found.

Kermit Rose