mersenneforum.org how to get F118 factor 1527888802614951*2^120+1?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2020-11-06, 00:12   #12
bbb120

Feb 2019
China

3B16 Posts

Quote:
 Originally Posted by Batalov That's irrelevant. (If all you have is a hammer, everything looks like a nail.) Peter Strasser searched really hard with software shown here and found this factor of F118, and that's the end of this story. It says it right there - he found it with mmff. That means - using a GPU. Now, how did I find this one? ...not just by running mmff. First, I was studying mmff's source for a week and then modified and experimented with it for a few weeks and when I was content with the new extended range (n in range high hundred-ish to low-200-ish) passing all tests, I ran it for several more months (and I paid a bunch for ~20 GPUs on AWS for several months) -- but I did get it. It was not easy, I will tell you that.
you know too much than me ,I only can write simple program.

2020-11-06, 00:28   #13
bbb120

Feb 2019
China

738 Posts

Quote:
 Originally Posted by Batalov That's irrelevant. (If all you have is a hammer, everything looks like a nail.) Peter Strasser searched really hard with software shown here and found this factor of F118, and that's the end of this story. It says it right there - he found it with mmff. That means - using a GPU. Now, how did I find this one? ...not just by running mmff. First, I was studying mmff's source for a week and then modified and experimented with it for a few weeks and when I was content with the new extended range (n in range high hundred-ish to low-200-ish) passing all tests, I ran it for several more months (and I paid a bunch for ~20 GPUs on AWS for several months) -- but I did get it. It was not easy, I will tell you that.
Fn=2^(2^n)+1 has factors in k*2^(n+2)+1 this form,
so we can test a primality on p=k*2^(n+2)+1 before we
calculate Fn Mod p, do you have any algorithm which can be more faster to get
factor?

 2020-11-06, 02:23 #14 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2·5·11·43 Posts Yes. And the code is already written for you. mmff, like you've been told.
2020-11-06, 02:50   #15
bbb120

Feb 2019
China

59 Posts

Quote:
 Originally Posted by VBCurtis Yes. And the code is already written for you. mmff, like you've been told.
reading codes whrite by others is not an easy thing,
so I only take interest in algorithm in it

2020-11-06, 03:44   #16
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

1101110012 Posts

Quote:
 Originally Posted by bbb120 reading codes whrite by others is not an easy thing, so I only take interest in algorithm in it
You don't have to read it, you just run it...

 2020-11-06, 03:48 #17 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 250616 Posts
 2020-11-06, 03:57 #18 Gary     "Gary" Aug 2015 Texas 10000002 Posts Going back to your original question, the answer depends on what you meant by "get the F118 factor": - If you just want to re-discover the factor of F118 for fun, you can do that using any of the "Sieve+trial division" programs listed at FermatSearch/Download by giving it a search range of N = 120, K = 1527888802614951. This will take just a fraction of a second to run. - If you want to find a new factor of F118 that is of similar size as 1527888802614951*2^120+1, that is no longer possible because for N = 120-129 all K values up to 3.2 * 10^15 have already been searched. You can find what has already been searched for any range of N at FermatSearch/STATS/Merge Tables. - If you want to try to find a new factor of F118 (or ay other Fermat number), go to the FermatSearch Merge Tables and, for your range of N, find the highest K searched so far. Then select a range of K just above that. For example, for N = 120 you could select 3.2 * 10^15 to 3.3 *10^15. Reserve the range via FermatSearch, select an appropriate program via the Download page, and then start your search. And then hope you are very, very lucky
2020-11-06, 04:45   #19
bbb120

Feb 2019
China

59 Posts

Quote:
 Originally Posted by Gary Going back to your original question, the answer depends on what you meant by "get the F118 factor": - If you just want to re-discover the factor of F118 for fun, you can do that using any of the "Sieve+trial division" programs listed at FermatSearch/Download by giving it a search range of N = 120, K = 1527888802614951. This will take just a fraction of a second to run. - If you want to find a new factor of F118 that is of similar size as 1527888802614951*2^120+1, that is no longer possible because for N = 120-129 all K values up to 3.2 * 10^15 have already been searched. You can find what has already been searched for any range of N at FermatSearch/STATS/Merge Tables. - If you want to try to find a new factor of F118 (or ay other Fermat number), go to the FermatSearch Merge Tables and, for your range of N, find the highest K searched so far. Then select a range of K just above that. For example, for N = 120 you could select 3.2 * 10^15 to 3.3 *10^15. Reserve the range via FermatSearch, select an appropriate program via the Download page, and then start your search. And then hope you are very, very lucky
I do not want to find any factor of fermat number ,because it is very difficult to find one ,I only want to know the algorithm behind it

2020-11-06, 05:15   #20
bsquared

"Ben"
Feb 2007

2·35·7 Posts

Quote:
 Originally Posted by bbb120 I do not want to find any factor of fermat number ,because it is very difficult to find one ,I only want to know the algorithm behind it
Gary has already hinted at it: "Sieve+trial division".

Trial division is the process that actually determines the factor. It uses modular exponentiation to check if the Fermat number is 0 modulo the potential factor. The process is similar to that for Mersenne's, which is well described here: https://www.mersenne.org/various/mat...rial_factoring

The sieve portion is a preprocessing step that eliminates numbers that can't be factors, leaving fewer to check for divisibility.

2020-11-06, 05:24   #21
bbb120

Feb 2019
China

59 Posts

Quote:
 Originally Posted by bsquared Gary has already hinted at it: "Sieve+trial division". Trial division is the process that actually determines the factor. It uses modular exponentiation to check if the Fermat number is 0 modulo the potential factor. The process is similar to that for Mersenne's, which is well described here: https://www.mersenne.org/various/mat...rial_factoring The sieve portion is a preprocessing step that eliminates numbers that can't be factors, leaving fewer to check for divisibility.
Quote:
 Originally Posted by bsquared The sieve portion is a preprocessing step that eliminates numbers that can't be factors, leaving fewer to check for divisibility
How to sieve ? I only know p=k*2^(n+2)+1 must be a prime,
so we can use primality to sieve any potential p=k*2^(n+2)+1,
is there any more efficient method to sieve potential p=k*2^(n+2)+1?

2020-11-06, 05:32   #22
Gary

"Gary"
Aug 2015
Texas

26 Posts

Quote:
 Originally Posted by bbb120 I do not want to find any factor of Fermat number ,because it is very difficult to find one ,I only want to know the algorithm behind it
The programs I am familiar with will test each Dk = k*2^n + 1 for a range of k to see if it divides any Fermat number. To do this, the program will first use a sieve to eliminate all Dk that are divisible by any of the first X primes. X may vary from a few thousand to a huge number, depending on the value of n. For each Dk that survives the sieve, the program may immediately test to see if 2^2^m + 1 mod Dk = 0 for each m <= n-2 by doing successive square / mod operations. Or the program may next do a probable prime test on Dk before testing for Fermat number divisibilities. The PRP test is more efficient if the program is testing Dk to see if it divides either a Fermat number or a Generalized Fermat Number: a^2^n + b^2^n.

Hope that helps a bit.

 Similar Threads Thread Thread Starter Forum Replies Last Post JuanTutors Factoring 11 2019-08-03 18:57 lycorn PrimeNet 11 2013-01-12 12:07 lfm Data 15 2010-03-30 21:18 ChriS Factoring 3 2006-05-29 17:57 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 13:39.

Sun Apr 11 13:39:25 UTC 2021 up 3 days, 8:20, 1 user, load averages: 1.96, 1.68, 1.56