20060910, 19:58  #1 
"Jason Goatcher"
Mar 2005
3×7×167 Posts 
Could someone explain how the Fermat factoring programs work?
Sorry to post about something not having to do with the Mersenne forum, but I'm hoping I'll get a faster response.
Right now, I'm running a program that's processing n=20002020 and k=1e610e6. I know it's doing numbers of the form k*2^n+1(I'm not even totally sure if it's doing both plus and minus 1). I know it annoys some people that I don't totally understand the math, but if someone could explain the basic process, if not the actual running of the programs, I'd appreciate it. One thing I want to know is what do I do with results I get from what I'm running now? 
20060911, 01:49  #2 
Sep 2002
296_{16} Posts 
What program are you running ?
When you wrote Fermat factoring do you mean factoring Fermat numbers ? If so, then they are numbers such as F5, the fifth Fermat number, F1 through F4 are prime. Fermat numbers take the form of 2^2^n + 1 and the factors are of the form k*2^(n+2) + 1. For example F5 means 2^2^5 + 1 = 2^32 + 1 = 4294967296 + 1 = 4294967297. and potential factors are k*2^(5+2) + 1 = k*2^7 + 1 = k*128 + 1 with k taking the values 1 through 33554432, 33554432 = 2^25 = 2^(327). It has been factored, of which two factors are 5*2^7 + 1 = 5*128 + 1 = 641 52347*2^7 + 1 = 52347*128 + 1 = 6700416 + 1 = 6700417 641 * 6700417 = 4294967297. 
20060912, 00:19  #3  
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
Quote:
I know that Fermat numbers are of the form 2^(2^n)+1 where n is a whole number greater than or equal to zero. I also know that factors are of the form k*2^n+1. The recommended program to run was pfgw. Well, pfgw's job is to generate probable primes within certain ranges. My range that I reserved from the Fermat factoring page was n=2000 to 2020 and k=1e6 to 10e6. I guess my question is: Is the output that project is looking for k/n pairs that are probable primes? Presumably, these would be tested to see if they're factors, but it's possible I'm wrong and am doing the wrong thing. I think I'll go ahead and post in the online user group. sorry to bother you guys. :) 

20060912, 02:25  #4 
"Mark"
Apr 2003
Between here and the
6,529 Posts 
It depends upon which program(s) you are using. If you use FermFact, then you must run the output through PFGW or LLR. With LLR you can do the primality test, then run the primes through PFGW using the gx and a2 switches to look for Fermat and GFN factors. You can sent Fermat factors to the people at FermatSearch and the GFN factors to Wilfrid Keller.
If you are using Leonid Durman's fermat.exe program, it just tests for Fermat divisibility. The same could be said for gmpfermat, the GMP based software that works similar to Leonid's program, but can be run on nonx86 CPUs. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Links to factoring programs  smh  Factoring  72  20210820 21:28 
Links to Factoring Programs  rogue  Factoring  32  20090917 11:40 
factoring programs  henryzz  Factoring  6  20070919 13:47 
Can anyone explain 'iterations' for factoring?  petrw1  PrimeNet  8  20070811 18:28 
looking for Fermat factoring programs  ixfd64  Factoring  1  20050908 12:13 