mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2020-11-07, 00:51   #23
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by Gary View Post
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.
I only know how to find factor of fermat number by writing mathematica code

my code to find F36 factor
Code:
Clear["Global`*"];
n=36;(*the nth fermat number*)
Do[p=k*2^(n+2)+1;(*probable factor*)
   If[PrimeQ[p],(*factor must be a prime*)
      aa=Mod[PowerMod[2,2^n,p]+1,p];(*nth fermat number mod p*)
      If[aa==0,(*if p is a divisor of fermat number*)
        Print[{k,p}];
        Break[]]],
   {k,1,100}]
result
Code:
{10,2748779069441}

Last fiddled with by bbb120 on 2020-11-07 at 01:11
bbb120 is offline   Reply With Quote
Old 2020-11-07, 14:48   #24
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·1,481 Posts
Default

Quote:
Originally Posted by bbb120 View Post
I only know how to find factor of fermat number by writing mathematica code

my code to find F36 factor
Code:
Clear["Global`*"];
n=36;(*the nth fermat number*)
Do[p=k*2^(n+2)+1;(*probable factor*)
   If[PrimeQ[p],(*factor must be a prime*)
      aa=Mod[PowerMod[2,2^n,p]+1,p];(*nth fermat number mod p*)
      If[aa==0,(*if p is a divisor of fermat number*)
        Print[{k,p}];
        Break[]]],
   {k,1,100}]
result
Code:
{10,2748779069441}
The following mindless Pari-GP script disclosed two factors in fairly short order.
Code:
? n=1;d=2^38;for(k=1,10000000,n+=d;if(gcd(n,210)==1,r=Mod(2,n);for(i=1,36,r=r^2);if(r==-1,print(k" "n))))
10 2748779069441
3759613 1033434552359452673
At Prime factors k*2n + 1 of Fermat numbers Fm and complete factoring status we find that these results are not new.

For m = 36, we find (results here listed in form odd k, n such that k*2n + 1 divides Fm, when, who).

5, 39, 1886, P. Seelhoff

3759613, 38, 02 Jan 1981, G. B. Gostin & P. B. McLaughlin

Note well the dates, and the first "who" on that second find.

I will pass on seeking the hardware that was used. It should be clear that the most important component is the gray grease in peoples' skulls.

Last fiddled with by Dr Sardonicus on 2020-11-07 at 14:54 Reason: Insert missing comma, right paren
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-07, 15:11   #25
mathwiz
 
Mar 2019

22×37 Posts
Default

Quote:
Originally Posted by bbb120 View Post
I only know how to find factor of fermat number by writing mathematica code
Again:
  1. Go to www.fermatsearch.org
  2. Pick an available range you want to work on.
  3. Download the appropriate software in Downloads, run it, report results.
  4. Repeat!
mathwiz is offline   Reply With Quote
Old 2020-11-07, 18:58   #26
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

26 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
3759613, 38, 02 Jan 1981, G. B. Gostin & P. B. McLaughlin

I will pass on seeking the hardware that was used.
Phil and I each discovered the F36 factor independently, and then collaborated on the Math Comp paper. I used a Motorola MC6800 processor based system where the hardware, OS, assembler and Fermat search program were all home-made. It was a fun extension of a project I started in grad school.
Gary is offline   Reply With Quote
Old 2020-11-07, 19:21   #27
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

23·317 Posts
Default

Fermat factor are of the form k*2^n+1

You have to either chose a low k, and a large n or the opposite. A very high k and a reasonnable n.
either are unlikely.
firejuggler is online now   Reply With Quote
Old 2020-11-07, 19:53   #28
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·727 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.
Actually for large n it is better to do a Proth test, which takes the same amount of time, but you could discover million+ digit prime (that is not divide any Fermat number).
And if it is prime then check if this divides a Fermat number or not.

Last fiddled with by R. Gerbicz on 2020-11-07 at 19:54
R. Gerbicz is offline   Reply With Quote
Old 2020-11-07, 20:25   #29
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100101010112 Posts
Quote:
Originally Posted by R. Gerbicz View Post
Actually for large n it is better to do a Proth test, which takes the same amount of time, but you could discover million+ digit prime (that is not divide any Fermat number).
And if it is prime then check if this divides a Fermat number or not.
Damn it! You had to give away our precious secret!


By the way, -- this reminds my doubts when I heard that there was a theory that the Fermat div probability was not merely ~1/k, and some folks invested a few billion-trillion GHz-hours in demonstrating that ...it probably may not be so. But that's probably a good topic for another, separate thread.
Quote:
Originally Posted by http://www.primegrid.com/forum_thread.php?id=8783
... it became clear that k = 3^9 = 19683 was unusually promising
Batalov is offline   Reply With Quote
Old 2020-11-07, 22:29   #30
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

802810 Posts
Default

Quote:
Originally Posted by Gary View Post
I used a Motorola MC6800 processor based system where the hardware, OS, assembler and Fermat search program were all home-made.
Tell us more!

Xyzzy is offline   Reply With Quote
Old 2020-11-08, 00:27   #31
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by mathwiz View Post
Again:
  1. Go to www.fermatsearch.org
  2. Pick an available range you want to work on.
  3. Download the appropriate software in Downloads, run it, report results.
  4. Repeat!
why download software from www.fermatsearch.org?
my mathematica code can get factor correctly,
and it is efficiently ,maybe not the most efficiently.
bbb120 is offline   Reply With Quote
Old 2020-11-08, 00:33   #32
mathwiz
 
Mar 2019

14810 Posts
Default

Quote:
Originally Posted by bbb120 View Post
why download software from www.fermatsearch.org?
my mathematica code can get factor correctly,
and it is efficiently ,maybe not the most efficiently.
It's not the most efficient. You are of course free to search with Mathematica, but the programs at that site are generally faster.

Of course, you're encouraged to read, understand, and potentially optimize the code for those programs too!
mathwiz is offline   Reply With Quote
Old 2020-11-10, 00:20   #33
bbb120
 
bbb120's Avatar
 
Feb 2019
China

738 Posts
Default

Quote:
Originally Posted by mathwiz View Post
It's not the most efficient. You are of course free to search with Mathematica, but the programs at that site are generally faster.

Of course, you're encouraged to read, understand, and potentially optimize the code for those programs too!
do you find any factor of fermat number ?
bbb120 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 12:13.

Sun Apr 11 12:13:26 UTC 2021 up 3 days, 6:54, 1 user, load averages: 1.48, 1.40, 1.39

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.