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

2020-11-07, 00:51   #23
bbb120

Feb 2019
China

59 Posts

Quote:
 Originally Posted by Gary 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

2020-11-07, 14:48   #24
Dr Sardonicus

Feb 2017
Nowhere

5×19×47 Posts

Quote:
 Originally Posted by bbb120 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

2020-11-07, 15:11   #25
mathwiz

Mar 2019

149 Posts

Quote:
 Originally Posted by bbb120 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.
4. Repeat!

2020-11-07, 18:58   #26
Gary

"Gary"
Aug 2015
Texas

26 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

 2020-11-07, 19:21 #27 firejuggler     Apr 2010 Over the rainbow 9E916 Posts 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.
2020-11-07, 19:53   #28
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101101100102 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.
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

2020-11-07, 20:25   #29
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

939010 Posts
Quote:
 Originally Posted by R. Gerbicz 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

2020-11-07, 22:29   #30
Xyzzy

"Mike"
Aug 2002

3·7·383 Posts

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

2020-11-08, 00:27   #31
bbb120

Feb 2019
China

59 Posts

Quote:
 Originally Posted by mathwiz Again:Go to www.fermatsearch.org Pick an available range you want to work on. Download the appropriate software in Downloads, run it, report results. Repeat!
my mathematica code can get factor correctly,
and it is efficiently ,maybe not the most efficiently.

2020-11-08, 00:33   #32
mathwiz

Mar 2019

149 Posts

Quote:
 Originally Posted by bbb120 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!

2020-11-10, 00:20   #33
bbb120

Feb 2019
China

59 Posts

Quote:
 Originally Posted by mathwiz 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 ?

 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 10:38.

Sat Apr 17 10:38:05 UTC 2021 up 9 days, 5:18, 0 users, load averages: 1.74, 1.96, 2.24