GIMPS' first Fermat factor!

[ATH]

http://primes.utm.edu/glossary/xpage/FermatNumber.html

http://mathworld.wolfram.com/FermatNumber.html

Fermat number F_n = 2^2[sup]n[/sup]+1 and it can be shown that any factor of a fermat number F_n is of the form k*2ⁿ⁺²+1.

So you found a factor of 2^2[sup]19[/sup]+1 = 2⁵²⁴²⁸⁸+1 and the factor:
37590055514133754286524446080499713 = 17924335248057248252165053406 * 2²¹+1. ( = 8962167624028624126082526703 * 2²²+1 factors are usually written with odd k).

Here is a list of all known fermat factors:
http://www.prothsearch.net/fermat.html


The factor was found by Elliptic Curve Factorization Method (ECM) which is a probabilistic method:
http://www.mersennewiki.org/index.php/ECM
http://en.wikipedia.org/wiki/Lenstra..._factorization

[Random Poster]

Why hasn't anyone proven the compositeness of the cofactor of F25? It's been over ten years since F24 was proven composite, and computers have gotten a lot faster in that time, so it shouldn't take too much effort.

[TimSorbet]

Originally Posted by Random Poster

Why hasn't anyone proven the compositeness of the cofactor of F25? It's been over ten years since F24 was proven composite, and computers have gotten a lot faster in that time, so it shouldn't take too much effort.

Are you sure nobody has? It's certainly not a trivial effort (I'm estimating 38 days at 0.1 secs/iter on one core of my 2.5 GHz Athlon; I'd guess an i7 with all cores working on it could crank it out in under a week) but if the cofactor of F25 is still unknown it should be done.
Unless I did something wrong, this is the line you'd use in Prime95:

PRP=1,2,33554432,1,0,0,"25991531462657,204393464266227713,2170072644496392193"

[akruppa]

Indeed. I think that this worktodo.txt line would work

PRP=1,2,33554432,1,"25991531462657,204393464266227713,2170072644496392193"

(please check before using it!)

Expected time is 19 days on a 2.16 GHz Core 2. Very feasible, but I can't do it at the moment. Anyone want to have a go?

Alex

[ATH]

I started it, and it looks like that line works and known factors check out.

Btw where is documentation for the PRP= line in Prime95? Nothing in readme.txt or undoc.txt.

[TimSorbet]

Originally Posted by ATH

I started it, and it looks like that line works and known factors check out.

Btw where is documentation for the PRP= line in Prime95? Nothing in readme.txt or undoc.txt.

whatsnew.txt:

11) Program can now do PRP tests of (k*b^n+c)/f.  Add a line worktodo.txt that
    looks like this:
        PRP=k,b,n,c[,how_far_factored,tests_saved][,known_factors]
    The optional how_far_factored (in bits) and tests_saved values are used
    to determine if P-1 factoring prior to the PRP test would be beneficial.
    The optional known_factors list is a quoted comma separated list of
    known factors of k*b^n+c.

[msft]

Hi,

I check 4th cofactor of Fermat 25 is conposite.

3^(((2^(2^25)+1)/(48413*2^29+1)/(1522849979*2^27+1)/(16168301139*2^27+1)-1)*48413*2^29*1522849979*2^27*16168301139*2^27) != 1 (mod 2^(2^25)+1).

Use Fermat Euler Theorem.

http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/

[akruppa]

Originally Posted by msft

(mod 2^(2^25)+1).

This bit worries me. Did it really use the full Fermat number as the modulus to test whether the result is congruent to 1?

Alex

[msft]

Originally Posted by akruppa

Did it really use the full Fermat number as the modulus to test whether the result is congruent to 1?

Alex

This is Fermat Euler Theorem.

[akruppa]

Oh! Right, you multiply the exponent by p-1 for the known prime factors. That works, of course.

Alex

[Random Poster]

Originally Posted by Mini-Geek

Are you sure nobody has?

Not completely sure, of course, but no one has reported it to Wilfrid Keller. I would certainly hope that any such result finds its way to his Fermat factors page.