mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2020-11-06, 00:12   #12
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
bbb120 is offline   Reply With Quote
Old 2020-11-06, 00:28   #13
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by Batalov View Post
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?
bbb120 is offline   Reply With Quote
Old 2020-11-06, 02:23   #14
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3·5·307 Posts
Default

Yes. And the code is already written for you. mmff, like you've been told.
VBCurtis is offline   Reply With Quote
Old 2020-11-06, 02:50   #15
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
bbb120 is offline   Reply With Quote
Old 2020-11-06, 03:44   #16
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

5078 Posts
Default

Quote:
Originally Posted by bbb120 View Post
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...
Viliam Furik is offline   Reply With Quote
Old 2020-11-06, 03:48   #17
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

5×11×167 Posts
Default


Uncwilly is online now   Reply With Quote
Old 2020-11-06, 03:57   #18
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

22×3×5 Posts
Default

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
Gary is offline   Reply With Quote
Old 2020-11-06, 04:45   #19
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by Gary View Post
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
bbb120 is offline   Reply With Quote
Old 2020-11-06, 05:15   #20
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default

Quote:
Originally Posted by bbb120 View Post
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.
bsquared is offline   Reply With Quote
Old 2020-11-06, 05:24   #21
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 View Post
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?
bbb120 is offline   Reply With Quote
Old 2020-11-06, 05:32   #22
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

22×3×5 Posts
Default

Quote:
Originally Posted by bbb120 View Post
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.
Gary is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I think I need to factor some more JuanTutors Factoring 11 2019-08-03 18:57
What a (TF) factor!!... lycorn PrimeNet 11 2013-01-12 12:07
big factor lfm Data 15 2010-03-30 21:18
New Factor of F11 (?) ChriS Factoring 3 2006-05-29 17:57
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38

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

Mon Jan 18 00:45:23 UTC 2021 up 45 days, 20:56, 0 users, load averages: 2.32, 2.03, 1.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.