 mersenneforum.org Could someone explain how the Fermat factoring programs work?
 Register FAQ Search Today's Posts Mark Forums Read 2006-09-10, 19:58 #1 jasong   "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=2000-2020 and k=1e6-10e6. 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?   2006-09-11, 01:49 #2 dsouza123   Sep 2002 10100101102 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^(32-7). 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.   2006-09-12, 00:19   #3
jasong

"Jason Goatcher"
Mar 2005

3·7·167 Posts Quote:
 Originally Posted by dsouza123 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^(32-7). 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.
I apologize, once again I've caused confusion.

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. :)   2006-09-12, 02:25 #4 rogue   "Mark" Apr 2003 Between here and the 3·11·191 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 gmp-fermat, the GMP based software that works similar to Leonid's program, but can be run on non-x86 CPUs.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post smh Factoring 71 2019-02-21 22:33 rogue Factoring 32 2009-09-17 11:40 henryzz Factoring 6 2007-09-19 13:47 petrw1 PrimeNet 8 2007-08-11 18:28 ixfd64 Factoring 1 2005-09-08 12:13

All times are UTC. The time now is 12:44.

Fri May 7 12:44:26 UTC 2021 up 29 days, 7:25, 0 users, load averages: 2.35, 2.55, 2.71