20040228, 00:30  #1 
Sep 2002
2×331 Posts 
Program to factor F14
I have written a program to find the smallest factor of F14.
F14 is the fourteenth fermat number, 2^(2^14) + 1. Given m = 14, n = m+2 = 16, each factor of F14 is in the form k*2^n + 1 = k*2^16 + 1 = k * 65536 + 1. with k an integer in the range 1..2^2401. F14 is the smallest composite fermat number without a known factor. It is determined to be composite by There is a conjecture that the smallest factor of Fermat numbers is less than 2^(16*n) = 2^(16*16) = 2^256. Code:
Pseudo code is. f = 1 b = 65536 for k = 1 to 2^240  1 do f = k * b + 1 if (f14 mod f) = 0 then write( f is a factor of F14 ) exitfor endif endfor better pseudo code factor_found = FALSE f = 65536 + 1 while (f < 2^256) and (factor_found = FALSE) do if isprime(f) then ans = f14 mod f if (ans = 0) then factor_found = TRUE write( f ) endif endif f = f + 65536 endwhile 
20040228, 19:05  #2 
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} Posts 
This pseudocode certainly seems to work logically. In actual practice, rather than performing the isprime(f) calculation, the program can be optimized by sieving out f divisible by small primes and doing the f14 mod f calculation on any f remaining after sieving  the programs written by Leonid Durman (fermat.exe) and Tony Forbes (MFAC) do this. Even if optimized and run on a fast PC, I estimate that the program will have to run around 10^24 years before it is even checking possible factors that might have been missed by the Elliptic Curve Method, and if it doesn't find a factor, it will have to run around 10^56 years before it reaches k = 2^240 and stops. If you translate this pseudocode into an actual program, I hope you have a lot of patience!

20040228, 21:44  #3 
Sep 2002
2·331 Posts 
Any other ways to optimize, other programs that are tackling the problem ?
Doing the sieve before hand and modding what is left is probably equivalent to doing the prime test just when needed. It requires less space doing it just when needed, no need to hold all the values remain. Running it with random starting points (values of at least 2^208) will test numbers beyond the typical ECM ranges so not duplicate ECM efforts. The items that optimization by algorithm or code tweaks could help: The mod function, many different algorithms and code tweaks available largest amount of time to be saved. The isprime function, straight forward no obvious optimizations. The increment function, not much to optimize. The language/compiler can make a difference, I wrote a version in delphi 4 as a console (text mode) program, in C or Assembly it may be quicker. If the compiler supports any of the SIMD instructions MMX,3DNow,SSE/SSE2 there could be some gain in speed. 
20040229, 15:15  #4 
Aug 2002
2^{2}×3×709 Posts 
Even if you made it a million times faster wouldn't it still take a super long time to run?
I mean, even though 10^{50} years is a lot less than 10^{56} years, it still seems like a long time to me... (Or am I missing something?) 
20040301, 01:15  #5 
Sep 2002
2·331 Posts 
ECM factoring uses random curves and would take decades to check
just the 50 digit numbers, factoring random values closer to the 77 digit limit could find the small factor of F14. Making it as efficient as possible is desirable just as it is for Prime95, with all the optimizations both algorithmic ( sieving, mod 8, small prime tests ) and coding ( assembly ) Prime95 has become incredibly fast at trial factoring, using DWT to do multiplication has eliminated doing mods in LL. An exhaustive search by trial factoring of F14 is unrealistic but tests from random starting points for some fixed amount of iterations, might find it in some resonable amount of time. 
20040301, 02:30  #6 
"Mark"
Apr 2003
Between here and the
53·127 Posts 
Last year, I had written a GMP based program to find factors to Fermat numbers. It is as fast as Leonid's fermat.exe on some CPUs and faster on others. It can be compiled and run on any CPU. You can find the source at:
http://groups.yahoo.com/group/Fermat...es/GMPFermat/ 
20040301, 19:58  #7 
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} Posts 
quote:
"ECM factoring uses random curves and would take decades to check just the 50 digit numbers, factoring random values closer to the 77 digit limit could find the small factor of F14." My estimate of 16 years or so is still much more hopeful than the 10^29 years it would take to find 50digit factors by trial factoring. 70digit factors are a big jump, but I still estimate that a project the size of GIMPS could find any 70digit factors in less than a year. Sure, you might be phenomenally lucky and just happen to pick the right range, but you might get lucky and find that factor on the very first curve also. (Of course, it is hard to imagine 30,000 people getting as excited over finding a 70digit factor as over finding a recordsized prime, but that's a different matter. At least we are fairly certain another Mersenne prime will show up sooner or later, but there is no guarantee that F14 has a factor of less than 77 digits!) 
20050911, 13:35  #8  
Jan 2005
13 Posts 
Fermat's method of factoring program using GMP
Quote:
Thank you Carlos 

20050911, 15:28  #9 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
>I have tried to download your program from Yahoo Groups but I need to be a member
>of FermatNumbers! How do I download your program? Become a member of FermatNumbers? Alex Last fiddled with by akruppa on 20050911 at 15:29 
20050911, 18:20  #10  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11,483 Posts 
Quote:
You should be given an award for your skill in stating the bleeding obvious Paul 

20050911, 22:31  #11 
Aug 2002
2^{2}·3·709 Posts 
If you email me the binary I can attach it to this forum... Or you could upload it to the wiki...
(I hate sites that you have to join to access files and stuff!) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
My factor program...  Xyzzy  Programming  18  20140726 15:42 
New program to fully factor with GMPECM  rogue  GMPECM  51  20090601 12:53 
C program to factor using GMPECM and msieve  lazy  GMPECM  6  20070616 18:12 
Where I find the best program to it factor keys? I use AMD.  chrow  Factoring  5  20040219 10:15 
New program to test a single factor  dsouza123  Programming  6  20040113 03:53 