LINKS
CONTACTS



 
Productivity
Comparative characteristic of various algorithms realized today.
The formula is approximate to the experimental data and computed on a Intel Core i5 processor clocked at 3.00 GHz.

Compare relative speed of different processors with this Excel file.
George Woltman's mmff.exe works for 27<N<223.

 

K per second
CPU Only GPU
n Fermat GMP-Fermat pmfs Feromant FermFact+pfgw FeromantCUDA mmff ppsieve+pfgw
29 30,000,000 48,000,000 1,900,000,000
32 27,000,000 46,780,000 7,000,000 32,000,000 637,000,000 1,820,000,000 50,000
36 24,000,000 43,660,000 6,200,000 32,000,000 625,000,000 1,600,000,000 60,000
40 21,000,000 40,760,000 5,700,000 32,000,000 50,000 625,000,000 1,000,000,000 65,000
44 16,500,000 38,630,000 5,100,000 32,000,000 50,000 581,000,000 900,000,000 75,000
48 3,300,000 36,440,000 4,700,000 32,000,000 45,000 408,000,000 800,000,000 65,000
54 3,000,000 33,850,000 4,200,000 35,000,000 40,000 402,000,000 750,000,000 50,000
60 2,600,000 31,800,000 3,700,000 32,000,000 35,000 386,000,000 650,000,000 45,000
80 1,400,000 17,380,000 2,500,000 25,000,000 30,000 309,000,000 350,000,000 40,000
100 1,250,000 14,140,000 2,000,000 15,310,000 25,000 309,000,000 300,000,000 33,000
150 530,000 6,600,000 1,130,000 12,200,000 19,000 203,000,000 130,000,000 25,000
200 375,000 5,700,000 700,000 9.100,000 17,500 167,000,000 90,000,000 23,000
300 175,000 1,360,000 460,000 3,000,000 15,000 90,200,000 20,000
400 95,000 810,000 290,000 1,000,000 9,750 48,300,000 15,000
600 39,000 266,000 145,000 500,000 7,600 13,750
800 20,000 107,000 82,300 200,000 6,000 12,500
1000 11,000 60,000 55,000 113,000 5,144 11,574
2000 2,000 9,000 12,800 17,000 2,415 3,858
3000 680 2,600 4,600 4,025 1,781 2,315
5000 180 350 1,286 965 1,052
10000 18 45 235 351 429
20000 2.6 6 45 172 223
30000 0.91 0.94 84 109
50000 20 25
100000 1.0 1.2

 

Factor search for very small Fermat numbers F12 - F28

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:.

Small and average Fermat numbers F28 ~ F2000

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.

Large and very large Fermat numbers ~F2000 ~ F500000

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: FermFact 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.


Copyright MoreWare 2003 ...