TIME COMPARISONS

Table 1: Products of two nearby primes

number 1number 2number 3number 4
BasicDivision0.051.718.5815.81
William's P+10.082.042.720.11
Pollard's P-10.120.721.90.39
Pollard's Rho0.020.330.590.61
Lenstra's ECM0.080.110.560.93
Shank Squares0.020.020.030.05
Dixon Squares0.030.050.020.03
Fermat Method0.010.020.020.02

Where:
number 1 = 3980021 = 1993 x 1997
number 2 = 16831170221 = 129733 x 129737
number 3 = 431589872009 = 656951 x 656959
number 4 = 1469322167111 = 1212121 x 1212191

Table 2: Products of three nearby primes

number 1number 2number 3number 4
Dixon Squares0.110.611.087.98
William's P+10.110.250.862.27
BasicDivision0.070.140.262.72
Pollard's P-10.260.680.281.74
Lenstra's ECM0.120.670.820.70
Shank Squares0.020.100.071.53
Pollard's Rho0.050.050.070.29

Where:
number 1 = 7956061979 = 1993 x 1997 x 1999
number 2 = 110154695923 = 4789 x 4793 x 4799
number 3 = 1019829472003 = 10061 x 10067 x 10069
number 4 = 1005660644975291 = 100183 x 100189 x 100193

Table 3: Products of three arbitrary primes

number 1number 2number 3number 4
Shank Squares0.441.09169.51-
Dixon Squares0.060.4545.20315.47
Pollard's P-10.230.905.46-
BasicDivision0.110.2213.1228.26
William's P+10.570.306.59137.25
Lenstra's ECM0.530.466.7810.94
Pollard's Rho0.070.060.141.31

Where:
number 1 = 14960418503 = 179 x 8467 x 9871
number 2 = 8355211084777 = 1163 x 12347 x 581857
number 3 = 416531649825896503 = 12983 x 987533 x 32487877
number 4 = 153674304751986405509 = 762479 x 1276237 x 157921783

• Stay tuned... When code gets better, these charts can change!

Notes:
1. Times are in seconds
2. Entries are ranked in order of overall efficiency - worst to best
3. a "-" means it took longer than I was willing to wait
4. If an algorithm is not listed, either it took too long to factor, or I don't have the code available.
5. Times from a 100MHz Sparcstation running Solaris 2.3
6. Parameters used:
• Basic Division: "smart" alg.
• William P+1: p=4
• Pollard P-1: a=2, K=2
• Lenstra ECM: no K argument (automatic K selection)
7. It is obvious from these results that pollards p-1 and lenstra's algorithms could use a little work. This can be reflected in the bad choices in K's for the two algorithms. A smarter choice function for K is needed in both cases.

Back to the factoring page