TIME COMPARISONS
Table 1: Products of two nearby primes
| number 1 | number 2 | number 3 | number 4
|
| BasicDivision | 0.05 | 1.71 | 8.58 | 15.81
|
|---|
| William's P+1 | 0.08 | 2.04 | 2.72 | 0.11
|
|---|
| Pollard's P-1 | 0.12 | 0.72 | 1.9 | 0.39
|
|---|
| Pollard's Rho | 0.02 | 0.33 | 0.59 | 0.61
|
|---|
| Lenstra's ECM | 0.08 | 0.11 | 0.56 | 0.93
|
|---|
| Shank Squares | 0.02 | 0.02 | 0.03 | 0.05
|
|---|
| Dixon Squares | 0.03 | 0.05 | 0.02 | 0.03
|
|---|
| Fermat Method | 0.01 | 0.02 | 0.02 | 0.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 1 | number 2 | number 3 | number 4
|
| Dixon Squares | 0.11 | 0.61 | 1.08 | 7.98
|
|---|
| William's P+1 | 0.11 | 0.25 | 0.86 | 2.27
|
|---|
| BasicDivision | 0.07 | 0.14 | 0.26 | 2.72
|
|---|
| Pollard's P-1 | 0.26 | 0.68 | 0.28 | 1.74
|
|---|
| Lenstra's ECM | 0.12 | 0.67 | 0.82 | 0.70
|
|---|
| Shank Squares | 0.02 | 0.10 | 0.07 | 1.53
|
|---|
| Pollard's Rho | 0.05 | 0.05 | 0.07 | 0.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 1 | number 2 | number 3 | number 4
|
| Shank Squares | 0.44 | 1.09 | 169.51 | -
|
|---|
| Dixon Squares | 0.06 | 0.45 | 45.20 | 315.47
|
|---|
| Pollard's P-1 | 0.23 | 0.90 | 5.46 | -
|
|---|
| BasicDivision | 0.11 | 0.22 | 13.12 | 28.26
|
|---|
| William's P+1 | 0.57 | 0.30 | 6.59 | 137.25
|
|---|
| Lenstra's ECM | 0.53 | 0.46 | 6.78 | 10.94
|
|---|
| Pollard's Rho | 0.07 | 0.06 | 0.14 | 1.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:
- Times are in seconds
- Entries are ranked in order of overall efficiency - worst to best
- a "-" means it took longer than I was willing to wait
- If an algorithm is not listed, either it took too long to
factor, or I don't have the code available.
- Times from a 100MHz Sparcstation running Solaris 2.3
- 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)
- 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
Back to my home page
Back to the pslc home page
Paul Herman
pherman@frenchfries.net
Last Updated: Jun 17, 1997