mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-07-20, 04:29   #34
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

19×181 Posts
Default

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

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

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

So you found a factor of 22[sup]19[/sup]+1 = 2524288+1 and the factor:
37590055514133754286524446080499713 = 17924335248057248252165053406 * 221+1. ( = 8962167624028624126082526703 * 222+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

Last fiddled with by ATH on 2009-07-20 at 04:37
ATH is offline   Reply With Quote
Old 2009-07-22, 20:21   #35
Random Poster
 
Random Poster's Avatar
 
Dec 2008

17910 Posts
Default

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.
Random Poster is offline   Reply With Quote
Old 2009-07-22, 20:40   #36
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101101112 Posts
Default

Quote:
Originally Posted by Random Poster View Post
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:
Code:
PRP=1,2,33554432,1,0,0,"25991531462657,204393464266227713,2170072644496392193"
TimSorbet is offline   Reply With Quote
Old 2009-07-22, 20:42   #37
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Indeed. I think that this worktodo.txt line would work
Code:
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
akruppa is offline   Reply With Quote
Old 2009-07-23, 09:53   #38
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

19·181 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2009-07-23, 12:00   #39
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts
Default

Quote:
Originally Posted by ATH View Post
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:
Code:
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.
TimSorbet is offline   Reply With Quote
Old 2009-07-23, 12:01   #40
msft
 
msft's Avatar
 
Jul 2009
Tokyo

2×5×61 Posts
Default

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/
msft is offline   Reply With Quote
Old 2009-07-23, 12:07   #41
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by msft View Post
(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
akruppa is offline   Reply With Quote
Old 2009-07-23, 12:22   #42
msft
 
msft's Avatar
 
Jul 2009
Tokyo

61010 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
msft is offline   Reply With Quote
Old 2009-07-23, 12:28   #43
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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

Alex
akruppa is offline   Reply With Quote
Old 2009-07-23, 20:40   #44
Random Poster
 
Random Poster's Avatar
 
Dec 2008

B316 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
Random Poster is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GIMPS' second Fermat factor! rajula Factoring 103 2019-03-12 04:02
New Fermat factor found! ET_ Factoring 5 2011-01-13 11:40
New Fermat factor! ET_ Factoring 21 2010-03-15 21:02
New Fermat factor! ET_ Factoring 42 2008-12-01 12:50
New Fermat factor found! ET_ Factoring 3 2004-12-14 07:23

All times are UTC. The time now is 15:18.


Mon Feb 6 15:18:07 UTC 2023 up 172 days, 12:46, 1 user, load averages: 1.86, 1.64, 1.47

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔