Compare relative speed of different processors with this Excel file.
George Woltman's mmff.exe works for 27<N<223.
| CPU Only | GPU | |||||||
|---|---|---|---|---|---|---|---|---|
| n | Fermat | GMP-Fermat | pmfs | Feromant | gfndsieve+pfgw | FeromantCUDA | mmff | ppsieve+pfgw |
| 29 | 30,000,000 | 48,000,000 | 1,900,000,000 | |||||
| 32 | 27,000,000 | 46,780,000 | 9,000,000 | 40,760,870 | 637,000,000 | 1,820,000,000 | 50,000 | |
| 36 | 24,000,000 | 43,660,000 | 8,000,000 | 40 588 808 | 625,000,000 | 1,600,000,000 | 60,000 | |
| 40 | 21,000,000 | 40,760,000 | 7,015,195 | 40,262,485 | 625,000,000 | 1,000,000,000 | 65,000 | |
| 44 | 16,500,000 | 38,630,000 | 6,100,000 | 39,968,771 | 581,000,000 | 900,000,000 | 75,000 | |
| 48 | 3,300,000 | 36,440,000 | 5,380,321 | 39,497,981 | 408,000,000 | 800,000,000 | 65,000 | |
| 54 | 3,000,000 | 33,850,000 | 5,000,000 | 38,814,351 | 402,000,000 | 750,000,000 | 50,000 | |
| 60 | 2,600,000 | 31,800,000 | 4,645,618 | 38,209,357 | 386,000,000 | 650,000,000 | 45,000 | |
| 80 | 1,400,000 | 17,380,000 | 3,422,943 | 20,343,562 | 309,000,000 | 350,000,000 | 40,000 | |
| 100 | 1,250,000 | 14,140,000 | 2,497,638 | 19,959,482 | 309,000,000 | 300,000,000 | 33,000 | |
| 150 | 530,000 | 6,600,000 | 1,615,000 | 11,018,064 | 203,000,000 | 130,000,000 | 25,000 | |
| 200 | 375,000 | 5,700,000 | 1,075,416 | 11,106,808 | 24,500 | 167,000,000 | 90,000,000 | 23,000 |
| 300 | 175,000 | 1,360,000 | 579,399 | 4,128,563 | 21,000 | 90,200,000 | 20,000 | |
| 400 | 95,000 | 810,000 | 397,688 | 2,761,195 | 15.000 | 48,300,000 | 15,000 | |
| 600 | 39,000 | 266,000 | 196,240 | 984,174 | 14,200 | 26,200,000 | 13,750 | |
| 800 | 20,000 | 107,000 | 105,529 | 275,754 | 13,000 | 12,500 | ||
| 1000 | 11,000 | 60,000 | 69.944 | 158,454 | 12,000 | 11,574 | ||
| 2000 | 2,000 | 9,000 | 15,269 | 25,646 | 5,000 | 3,858 | ||
| 3000 | 680 | 2,600 | 5,788 | 7,779 | 3,000 | 2,315 | ||
| 5000 | 180 | 350 | 1,624 | 1,666 | 1,500 | 1,052 | ||
| 10000 | 18 | 45 | 293.78 | 209 | 1,000 | 429 | ||
| 20000 | 2.6 | 6 | 50.78 | 26 | 500 | 223 | ||
| 30000 | 0.91 | 0.94 | 19.15 | 9 | 160 | 109 | ||
| 50000 | 5.92 | 2 | 30 | 25 | ||||
| 100000 | 0.8735 | 0.4 | 1.5 | 1.2 | ||||
Richard Crandall, George Woltman and now Fermatsearch, maintain a project to search factors for small Fermat numbers using ECM (Elliptic Curve Method).
The divisor can have up to 60 digits. Prime95, written by George Woltman, and GMP-ECM, are the best programs for ECM.
Numbers up to F28 are tested using the ECM up to a limit where other factorization methods are useless (see this link),
so
we use modular arithmetics for Fermat numbers greater than F28:.
When N grows, scholar mltiplicatio becomes inefficient. Other faster multiplication algorithms are chosen.
One of the most used multiplication algorithms on this range is the modular Montgomery algorithm for both multiplication and exponentiation.
Other more efficient methods are Toon, Karatsuba and FFT multilication; they are faster but harder to implement. Programs based on GMP library automatically choose the best algorithm for the actual problem.
For such superhuge numbers, modular arithmetics is not enough. Square multiplying becomes time-critical.
For this task the program should use FFT (Fast Fourier Transform). The actual state of the art is reached using the following programs: gfndsieve or ppsieve (sieve) + latest PFGW.
If you use pre-sieved numbers, GeneFer is today the fastest program for the search for a 500,000+ digit prime.