mersenneforum.org Program to factor F14
 Register FAQ Search Today's Posts Mark Forums Read

 2004-02-28, 00:30 #1 dsouza123     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^240-1. 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
 2004-02-28, 19:05 #2 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 25·5·7 Posts This pseudo-code 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 pseudo-code into an actual program, I hope you have a lot of patience!
 2004-02-28, 21:44 #3 dsouza123     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.
 2004-02-29, 15:15 #4 Xyzzy     Aug 2002 2×17×251 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 1050 years is a lot less than 1056 years, it still seems like a long time to me... (Or am I missing something?)
 2004-03-01, 01:15 #5 dsouza123     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.
 2004-03-01, 02:30 #6 rogue     "Mark" Apr 2003 Between here and the 5×29×47 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/GMP-Fermat/
 2004-03-01, 19:58 #7 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 46016 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 50-digit factors by trial factoring. 70-digit factors are a big jump, but I still estimate that a project the size of GIMPS could find any 70-digit 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 70-digit factor as over finding a record-sized 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!)
2005-09-11, 13:35   #8
Carlos

Jan 2005

13 Posts
Fermat's method of factoring program using GMP

Quote:
 Originally Posted by rogue 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/GMP-Fermat/

Thank you
Carlos

 2005-09-11, 15:28 #9 akruppa     "Nancy" Aug 2002 Alexandria 2,467 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 2005-09-11 at 15:29
2005-09-11, 18:20   #10
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

1157710 Posts

Quote:
 Originally Posted by akruppa >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
Nice!

You should be given an award for your skill in stating the bleeding obvious

Paul

 2005-09-11, 22:31 #11 Xyzzy     Aug 2002 2×17×251 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!)

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Programming 18 2014-07-26 15:42 rogue GMP-ECM 51 2009-06-01 12:53 lazy GMP-ECM 6 2007-06-16 18:12 chrow Factoring 5 2004-02-19 10:15 dsouza123 Programming 6 2004-01-13 03:53

All times are UTC. The time now is 03:00.

Wed Nov 30 03:00:03 UTC 2022 up 104 days, 28 mins, 0 users, load averages: 0.94, 0.81, 0.78