mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2006-09-10, 19:58   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

DB116 Posts
Default 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?
jasong is offline   Reply With Quote
Old 2006-09-11, 01:49   #2
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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.
dsouza123 is offline   Reply With Quote
Old 2006-09-12, 00:19   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Quote:
Originally Posted by dsouza123 View Post
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. :)
jasong is offline   Reply With Quote
Old 2006-09-12, 02:25   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

17·347 Posts
Default

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.
rogue is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Links to factoring programs smh Factoring 71 2019-02-21 22:33
Links to Factoring Programs rogue Factoring 32 2009-09-17 11:40
factoring programs henryzz Factoring 6 2007-09-19 13:47
Can anyone explain 'iterations' for factoring? petrw1 PrimeNet 8 2007-08-11 18:28
looking for Fermat factoring programs ixfd64 Factoring 1 2005-09-08 12:13

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

Sat Sep 19 03:48:30 UTC 2020 up 9 days, 59 mins, 0 users, load averages: 1.15, 1.06, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.