how to get F118 factor 1527888802614951*2^120+1?

[bbb120]

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

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

{10,2748779069441}

[Dr Sardonicus]

Originally Posted by bbb120

I only know how to find factor of fermat number by writing mathematica code

my code to find F36 factor

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

{10,2748779069441}

The following mindless Pari-GP script disclosed two factors in fairly short order.

? 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*2ⁿ + 1 of Fermat numbers F_m 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*2ⁿ + 1 divides F_m, 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.

[mathwiz]

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.
3. Download the appropriate software in Downloads, run it, report results.
4. Repeat!

[Gary]

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.

[firejuggler]

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.

[R. Gerbicz]

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.

[Batalov]

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.

Originally Posted by http://www.primegrid.com/forum_thread.php?id=8783

... it became clear that k = 3^9 = 19683 was unusually promising

[Xyzzy]

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!

[bbb120]

Originally Posted by mathwiz

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.

[mathwiz]

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!

[bbb120]

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 ?