## 19771Comparison of factor routines.

Expand Messages
• Dec 26, 2008
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