20040216, 15:50  #1 
Feb 2004
10111_{2} 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... 
20040216, 16:38  #2 
Banned
"Luigi"
Aug 2002
Team Italia
2^{2}×3×401 Posts 
I will post a copy of Durman's Feramt.exe as soon as I get home.
Luigi 
20040216, 18:50  #3 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
5^{2}·17 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^N1 ECM factoring. Then it is actually faster to test e.g. M262144 = 2^2621441 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. 
20040216, 19:36  #4  
Banned
"Luigi"
Aug 2002
Team Italia
2^{2}×3×401 Posts 
Quote:
PM me your email address and I'll send you the program! Luigi 

20040216, 21:27  #5 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011111_{2} 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 GMPECM. 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 Pmode and Mmode. Pmode does not run well on Pentium4's, as the Pmode multiplication routines have not incorporated SSE2 code. So if you have a Pentium4, you will want to run in Mmode. If you have an AMD Athlon or a Pentium3 based system, either mode works well, although even for these systems, Mmode is slightly more efficient. But if you want to concentrate on one particular Fermat number like F14, and you have a Pentium3 or Athlon, you will want to run in Pmode.
ECM and P1 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. 
20040217, 00:30  #6 
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 selfextracting 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. 
20040217, 07:53  #7 
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 Mmode 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 
20040217, 11:39  #8  
Nov 2003
3×5×11 Posts 
Quote:


20040217, 17:26  #9  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
24635_{8} Posts 
Quote:
Paul 

20040217, 22:34  #10 
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??????? 
20040217, 23:19  #11 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011111_{2} 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 + A*x^2 + B*x Different choices of s lead to different coefficients A and B. I wrote a rough nontechnical description of the algorithm in the Math thread under "Elliptic Curve Method  the theory": http://www.mersenneforum.org/showthread.php?t=194 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 factoring attempts at smallestremaining Mersenne numbers with no known factors  UberNumberGeek  Factoring  51  20170213 20:30 
What are the Primality Tests ( not factoring! ) for Fermat Numbers?  Erasmus  Math  46  20140808 20:05 
Factoring Fermat numbers  siegert81  Factoring  12  20110203 13:55 
Elliptic Curve Method factoring  Fermat numbers  philmoore  Math  131  20061218 06:27 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 