FAQ

Answers to frequently asked questions (FAQ) may be found below. If you have
a question that is not answered below, feel free to contact
Leonid Durman. or Luigi Morelli.

Known divisors

On Wilfrid Keller's page there is a detailed information of all known divisors

1. What are we searching for?

We are trying to find factors of Fermat Numbers. Fermat numbers
have a beautiful mathematical formula: F_{m}=2^{2^m}+1. If a divisor of a Fermat
number is found, it can always be expressed in the form: k.2^{n}+1, where n __>__ m+2.
Fermat numbers grow very rapidly. The first 33 (F_{0}..F_{32}) numbers are known to
be prime or composite. There are hardly more than 260 total known divisors
of Fermat Numbers. Many years of work will be spent seeking new Fermat
divisors.

2. Why are we searching?

This is a fascinating endeavor. Though there are few practical applications for Fermat divisors, the algorithms used for finding them have applications to other computing tasks. For example, the Fast Fourier Transform (FFT) was discovered over a century ago, but had no practical use until recently with computers and refined algorithms. Without this algorithm, many necessary tasks include those in medicine and imaging could not be done even with the most advanced computer.

3. What do I need to do to participate?

After having requested a range, download the program in the section DOWNLOAD and save it into any folder of your choice. Start the program and enter initial values for n and k. To have the program automatically start when restarting your computer, select “options” and “Windows Service” from the menu bar, or use a cron job if you are under Linux. Please email to me the values that you are testing and have completed. That is all you have to do. The program automatically does the rest.

4. What are my chances of finding a new divisor?

Not bad. If you persist in running the program, you should find a new divisor. The author of the program has found 4 new divisors in 9 months of testing. Other participants doing testing for divisors have also been fortunate. It is likely that 5-10 new divisors will be discovered each year. The difficulty of finding new divisors will grow logarithmically with time, but so is the speed of modern computers.

5. How much time should be spent running the program?

This depends on the nature of your computing activities. The program can work in background mode all day. Leaving the program running at night will cause no problems except for the use of a little electricity. Modern computer processors can work continuously for years without any consequences. They become outdated much faster that they “wear out.”

6. How will the program affect the other computer work?

It should have no effect at all. The program by default works at the lowest possible priority, preventing interference with other programs. The program already run on many computers without the users seeing any effects on their work. The program uses only unused computer cycles. Only about a few megabytes of memory are used for algorithm, arrays and visual library of components. Most modern computers have hundreds of mbytes.

7. What files does the program create and what do they contain?

The program "Fermat.exe" creates on 3 files in the same directory or folder where you copied the program. Fermat.ini contains temporary configuration data and values being tested. It updates about every 20-30 minutes. If the computer malfunctions and is switched off, you loose at most 20-30 minutes of work. Fermat.log is a file holds your calculation ranges. Results of your work are placed here. Please send me the file Fermat.log for updating the status of work. Finally, the most pleasing file is Results.txt that is only created when a Fermat number divisor is found. Each time the program is started, it reads this file and displays the information on the program panel. Even if you leave the program running for a week and restart it, you will see if a Fermat divisor was found.

8. Why do we test with n instead of m?

I too did not understand this difference initially. My first program found a divisor for a Fermat number. But looking carefully, having taken one n, we search at each step for a divisor for numbers Fj, F(j+1), F(j+2)… Fm.

9. What is the principle behind the program testing?

The answer is complex. The basis of the program is modular arithmetics and square multiplication algorithms. For large numbers, Yves Gallot’s Proth program uses a Fast Fourier Transformation (FFT) algorithm, but for factors with a small n<1500, FFT is slower than classical multiplication. … Calculating Fm=x(mod k.2^n+1) is a rather labor-consuming process, therefore it is necessary to exclude many divisors first. For example if it is known that k.2^n+1=0(mod 3), then it is possible to exclude all k, k+3, …, k+3*j. In general, the algorrithm allows the exclusion of approximately 90% of values of k. The program works about 10 times faster than direct division into the number k.2^n+1. All methods known to me for optimization of these two processes are now in use. Very interestingly, use of these algorithms for carrying out division does not need the division command at all. … The division command is replaced with the return multiplication command r=1/t. The command mul is carried out in four steps. The new Pentium 4 processor should speed up the calculations. It carries out the command "mul" in one step. The "mul" command is used frequently in the Fermat program.

10. What programming language is used for the program?

The entire computing algorithm is written in Assembler. There are no procedures or libraries to slow down the code. The interface was written using Delphi. It has required the visual library of components, therefore the program is a little bit large.

11. How many prime numbers are tested by the program to exclude a divisor? Method fast sieve.

30,000 or more. Version 4.4 enlarges the sieving process to improve speed, but requires a larger amount of phisical memory.

12. Is it possible to use the program NewPGen to speed up calculations with Fermat.exe?

All necessary calculations by Fermat.exe are carried out in the processor cache, using the optimized approach of Eratosthenes, which is faster than NewPGen.

13. Is there a difference in speed between processors?

I have not noticed any speed difference between the Celeron, PII, and PIII processors of the same clock speed. This is because the program uses so little cache memory that even the Celeron has enough. Your Celeron will feel like a PentiumIII while running this program! If you use an older processor such as the Pentium/MMX, there will be a noticeable difference. Fermat.exe is optimized for modern processors and is carried out much faster on them than on early processors. Athlon is confidently faster PIII on 20%-40%, due to best pipelining.

14. What does P6 mean in the program header?

P6 stands for the generation of the processor. Celeron, PII, PIII and Athlon are all of P6 generation.

15. Which program is better for similar calculations?

See DOWNLOAD section: there are fresh items of information on accessible and fast programs.

If you have not found the answer to your question here, please email the
author.

Copyright © MoreWare 2003 ...