Factoring Smallest Fermat Numbers

Erasmus · 2004-02-16, 15:50

Hi,

I was searching for some specialised factorization websites and found out that some relatively small Fermat numbers remain unfactored for 40 years.

INFO Fermat Numbers are of the form (2^N) + 1 where N is also a power of 2 ( not necessarily the exponent is prime unlike Mersenne )

If internet researches are up to date, F14 which is 4933 digits long has no known factors. Also, F20, F22, F24 is unfactored but they are slightly longer than F14 ( F20 is 315000 digits !! )

Anyway, these four Fermat numbers are proven to be composite, interesting thing is that F14 was proven composite in 1963, but there were no wondrous man searching for its factors.

My problem starts here, i am very bad at programming and computing skills, so i have doubt using giantint program to search for fermat factors.

any of you know some info about programs skilled specifically for factoring fermat numbers? I have proth and searching for generalised fermat right now, but i couldn't make it search for original fermat numbers. Is there a way to test F14 with Proth.EXE ???????

Thanks for your help and also if there is a GUI based fermat search program, i will appreciate...

ET_ · 2004-02-16, 16:38

I will post a copy of Durman's Feramt.exe as soon as I get home.

Luigi

patrik · 2004-02-16, 18:50

I have used Prime95 to try finding factors of Fermat numbers. I don't know how it compares to other programs.

If you have a Pentium 4 computer Prime95 is very fast on 2^N-1 ECM factoring. Then it is actually faster to test e.g. M262144 = 2^262144-1 than F17 = 2^131072+1, which you can do since M262144 = F17*F16*F15*...*F0.

Link: http://www.mersenne.org/ecm.htm and continue with the "Fermat numbers" link at the bottom of that page.

ET_ · 2004-02-16, 19:36

Quote:

Originally Posted by ET_

I will post a copy of Durman's Feramt.exe as soon as I get home.

Luigi

Whops! The upload is limited to 100 KB while the file is 288 KB.

PM me your email address and I'll send you the program!

Luigi

philmoore · 2004-02-16, 21:27

I think that Prime95 is currently the best available program for trying to factor the lowest Fermat numbers F12 through F26 by the elliptic curve method (ECM), although Alex Kruppa has suggested to me that it may actually be more efficient to factor F12 and maybe even F13 by running the first stage with Prime95 and the second stage with GMP-ECM. As Patrik has pointed out, you may use Prime95 to either run curves on a single Fermat number, or you can run on several Fermat numbers simultaneously. So for example, to run curves on F14, you can input your number as P16384 (= 2^(2^14) + 1), or you can run curves on M32768 (= 2^(2^15) - 1). The latter option will also look for factors of all the lower Fermat numbers as well, so it could conceivably find new factors of F12, F13, or F14 (the lower Fermat numbers have already been completely factored.) I call these two modes P-mode and M-mode. P-mode does not run well on Pentium-4's, as the P-mode multiplication routines have not incorporated SSE2 code. So if you have a Pentium-4, you will want to run in M-mode. If you have an AMD Athlon or a Pentium-3 based system, either mode works well, although even for these systems, M-mode is slightly more efficient. But if you want to concentrate on one particular Fermat number like F14, and you have a Pentium-3 or Athlon, you will want to run in P-mode.

ECM and P-1 factoring are probably the best methods for trying to factor the Fermat numbers up through F24 or so. But above this, ECM requires large amounts of memory, and trial factoring takes over as the best method. Leonid Durman's Fermat.exe program is a good trial factoring program for Fermat numbers up through F1000 or so.

dsouza123 · 2004-02-17, 00:30

Leonid Durman's Fermat.exe can be downloaded off the following page

http://web.archive.org/web/200306212...matsearch.org/

the downloaded file is packFermat.exe, it is really a self-extracting zip file containing Fermat.exe, Whatnew.eng, Whatnew.rus

When I downloaded it the last byte was cutoff (with a value 0) you will need a program to fix the zip file, such as pkzipfix, or any other that can extract a file from a minimally damaged zip file.

If you have frhed, free hex editor you can just add a byte with the value 0 to the end of the file and save.

Erasmus · 2004-02-17, 07:53

Really thanks for your interest on this subject,

I have a P4, so i think it will be better using M-mode for 2^14, but i have 2nd pack of questions now!

1- F14 is a very small number when compared to other numbers being tested in all projects, why anybody did not come up with a factorization?

2- I will first use ECM of Prime95 with M32768, i was not sure about parameters used, so here is what i entered :
B1 : 1 000 000
B2 : 2 900 000
# of curves : 100

After these instructions, prime95 started to iterate like this way :
...
...
[Feb 17 ...] At Prime 82279 Time thus far...
[Feb 17 ...] At Prime 82301 Time thus far...
...
...

And it is growing. Am i doing right for this exponent or is there an optimal set of instructions for finding the factors?

3- If there is some optimal set of instructions, how do they change for F17,F20,F22 ?

OR is there a limiting equation to calculate # of curves needed, bounds etc. for a specific exponent???

Thanks for all your help

nfortino · 2004-02-17, 11:39

Quote:

Originally Posted by Erasmus

OR is there a limiting equation to calculate # of curves needed, bounds etc. for a specific exponent???

You should follow the instructions at http://mersenne.org/ecm.htm. If you are factoring Fermat numbers, follow the Fermat status page link at the bottom of the page to see the status of the numbers you are interested in. If you are using M-mode to factor F14, F13 and F12, you probably want to use a B1 of 44,000,000. These curves will probably take a long time. If you are impatient, you could factor F14 directly with a B1 of 11,000,000, trading efficiency for psychological gain. Note that it would be even more inefficient to factor M32768, since the status page says both F13 and F12 have been finished up to that bound, making it very improbable that you will find a factor. Finally, I beleive that the factoring project uses the standard B2=100*B1.

xilman · 2004-02-17, 17:26

Quote:

Originally Posted by Erasmus

1- F14 is a very small number when compared to other numbers being tested in all projects, why anybody did not come up with a factorization?

Thanks for all your help

Because F14 is a very large number. It is over 16 thousand bits long. State of the art in factoring general numbers is currently 576 bits, and it's only just over 800 bits for numbers which can be treated by the Special Number Field Sieve. The NFSNET project is currently working on an integer which is larger than any which has so far been factored. That integer has 811 bits.

Paul

Erasmus · 2004-02-17, 22:34

Sure F14 is still a huge number with 4933 digits. But check the status of some fermat numbers ( F2478782 , http://www.prothsearch.net/fermat.html )
Its factor is with k=3 n=2478785

Of course factoring ordinary numbers are easy but i'm still surprised about F14 remaining with any factor known. Check the above URL to see more than 250 known factors for various Fermat numbers.

Anyway, i am trying hard with the help of philmoore, started ECM on Prime95 with B1=11000000, i wish i will come up with brand new factors!!!

ONE LAST QUESTION : What is the logic of running multiple curves ( e.g 10 curves with B1=11000000 ) without changing B1, won't it give the same results with previous curve???????

philmoore · 2004-02-17, 23:19

Notice that each time the program begins a new curve, it prints out a line like:
ECM on M32768: curve #7 with s=46930544369504, B1=11000000, B2=1100000000
The s value is chosen by a random number generator. Different values of s define different elliptic curves to use in the calculation. We don't know which values of s will find factors, but we try several hundred or several thousand curves, hoping that we will get lucky!

By the way, an elliptic curve can be thought of a structure on the set of all solutions to an equation of the form:
y^2 = x^3 + A*x^2 + B*x
Different choices of s lead to different coefficients A and B. I wrote a rough non-technical description of the algorithm in the Math thread under "Elliptic Curve Method - the theory":
http://www.mersenneforum.org/showthread.php?t=194

2004-02-16, 15:50	#1
Erasmus Feb 2004 23 Posts	Factoring Smallest Fermat Numbers Hi, I was searching for some specialised factorization websites and found out that some relatively small Fermat numbers remain unfactored for 40 years. INFO Fermat Numbers are of the form (2^N) + 1 where N is also a power of 2 ( not necessarily the exponent is prime unlike Mersenne ) If internet researches are up to date, F14 which is 4933 digits long has no known factors. Also, F20, F22, F24 is unfactored but they are slightly longer than F14 ( F20 is 315000 digits !! ) Anyway, these four Fermat numbers are proven to be composite, interesting thing is that F14 was proven composite in 1963, but there were no wondrous man searching for its factors. My problem starts here, i am very bad at programming and computing skills, so i have doubt using giantint program to search for fermat factors. any of you know some info about programs skilled specifically for factoring fermat numbers? I have proth and searching for generalised fermat right now, but i couldn't make it search for original fermat numbers. Is there a way to test F14 with Proth.EXE ??????? Thanks for your help and also if there is a GUI based fermat search program, i will appreciate...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors	UberNumberGeek	Factoring	51	2017-02-13 20:30
What are the Primality Tests ( not factoring! ) for Fermat Numbers?	Erasmus	Math	46	2014-08-08 20:05
Factoring Fermat numbers	siegert81	Factoring	12	2011-02-03 13:55
Elliptic Curve Method factoring - Fermat numbers	philmoore	Math	131	2006-12-18 06:27
Factoring Fermat Numbers	Axel Fox	Software	14	2003-07-04 18:57

2004-02-16, 16:38	#2
ET_ Banned "Luigi" Aug 2002 Team Italia 3×1,619 Posts	I will post a copy of Durman's Feramt.exe as soon as I get home. Luigi

2004-02-16, 18:50	#3
patrik "Patrik Johansson" Aug 2002 Uppsala, Sweden 110101001₂ Posts	I have used Prime95 to try finding factors of Fermat numbers. I don't know how it compares to other programs. If you have a Pentium 4 computer Prime95 is very fast on 2^N-1 ECM factoring. Then it is actually faster to test e.g. M262144 = 2^262144-1 than F17 = 2^131072+1, which you can do since M262144 = F17F16F15...F0. Link: http://www.mersenne.org/ecm.htm and continue with the "Fermat numbers" link at the bottom of that page.

2004-02-16, 21:27	#5
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2140₈ Posts	I think that Prime95 is currently the best available program for trying to factor the lowest Fermat numbers F12 through F26 by the elliptic curve method (ECM), although Alex Kruppa has suggested to me that it may actually be more efficient to factor F12 and maybe even F13 by running the first stage with Prime95 and the second stage with GMP-ECM. As Patrik has pointed out, you may use Prime95 to either run curves on a single Fermat number, or you can run on several Fermat numbers simultaneously. So for example, to run curves on F14, you can input your number as P16384 (= 2^(2^14) + 1), or you can run curves on M32768 (= 2^(2^15) - 1). The latter option will also look for factors of all the lower Fermat numbers as well, so it could conceivably find new factors of F12, F13, or F14 (the lower Fermat numbers have already been completely factored.) I call these two modes P-mode and M-mode. P-mode does not run well on Pentium-4's, as the P-mode multiplication routines have not incorporated SSE2 code. So if you have a Pentium-4, you will want to run in M-mode. If you have an AMD Athlon or a Pentium-3 based system, either mode works well, although even for these systems, M-mode is slightly more efficient. But if you want to concentrate on one particular Fermat number like F14, and you have a Pentium-3 or Athlon, you will want to run in P-mode. ECM and P-1 factoring are probably the best methods for trying to factor the Fermat numbers up through F24 or so. But above this, ECM requires large amounts of memory, and trial factoring takes over as the best method. Leonid Durman's Fermat.exe program is a good trial factoring program for Fermat numbers up through F1000 or so.

2004-02-17, 00:30	#6
dsouza123 Sep 2002 2×331 Posts	Leonid Durman's Fermat.exe can be downloaded off the following page http://web.archive.org/web/200306212...matsearch.org/ the downloaded file is packFermat.exe, it is really a self-extracting zip file containing Fermat.exe, Whatnew.eng, Whatnew.rus When I downloaded it the last byte was cutoff (with a value 0) you will need a program to fix the zip file, such as pkzipfix, or any other that can extract a file from a minimally damaged zip file. If you have frhed, free hex editor you can just add a byte with the value 0 to the end of the file and save.

2004-02-17, 07:53	#7
Erasmus Feb 2004 23 Posts	Factoring Fermats Really thanks for your interest on this subject, I have a P4, so i think it will be better using M-mode for 2^14, but i have 2nd pack of questions now! 1- F14 is a very small number when compared to other numbers being tested in all projects, why anybody did not come up with a factorization? 2- I will first use ECM of Prime95 with M32768, i was not sure about parameters used, so here is what i entered : B1 : 1 000 000 B2 : 2 900 000 # of curves : 100 After these instructions, prime95 started to iterate like this way : ... ... [Feb 17 ...] At Prime 82279 Time thus far... [Feb 17 ...] At Prime 82301 Time thus far... ... ... And it is growing. Am i doing right for this exponent or is there an optimal set of instructions for finding the factors? 3- If there is some optimal set of instructions, how do they change for F17,F20,F22 ? OR is there a limiting equation to calculate # of curves needed, bounds etc. for a specific exponent??? Thanks for all your help

2004-02-17, 22:34	#10
Erasmus Feb 2004 23 Posts	Sure F14 is still a huge number with 4933 digits. But check the status of some fermat numbers ( F2478782 , http://www.prothsearch.net/fermat.html ) Its factor is with k=3 n=2478785 Of course factoring ordinary numbers are easy but i'm still surprised about F14 remaining with any factor known. Check the above URL to see more than 250 known factors for various Fermat numbers. Anyway, i am trying hard with the help of philmoore, started ECM on Prime95 with B1=11000000, i wish i will come up with brand new factors!!! ONE LAST QUESTION : What is the logic of running multiple curves ( e.g 10 curves with B1=11000000 ) without changing B1, won't it give the same results with previous curve???????

2004-02-17, 23:19	#11
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2⁵·5·7 Posts	Notice that each time the program begins a new curve, it prints out a line like: ECM on M32768: curve #7 with s=46930544369504, B1=11000000, B2=1100000000 The s value is chosen by a random number generator. Different values of s define different elliptic curves to use in the calculation. We don't know which values of s will find factors, but we try several hundred or several thousand curves, hoping that we will get lucky! By the way, an elliptic curve can be thought of a structure on the set of all solutions to an equation of the form: y^2 = x^3 + Ax^2 + Bx Different choices of s lead to different coefficients A and B. I wrote a rough non-technical description of the algorithm in the Math thread under "Elliptic Curve Method - the theory": http://www.mersenneforum.org/showthread.php?t=194