mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-01-10, 06:55   #1
siegert81
 
Dec 2010

2·37 Posts
Default Factoring Fermat numbers

I just have some questions about what programs/approaches to take in order to find a new Fermat divisor.

If I wanted to find a factor of F20, what's the best program/approach? What if, instead, I wanted to find a factor of F200? F2000? F20000? F200000?

I began looking for proth primes of the form k*2^n+1 where 500,000<k<1,000,000 and n>20,000 (testing one n value at a time). So far, I've found dozens of primes, but none of them are Fermat factors.

I also began testing for 5,000,000<k<10,000,000 and n>8,000. I've found hundreds of primes at this level, but none of them are Fermat factors.

Do I need to just keep testing for much longer periods of time, or should I change my entire approach?

Thanks for any help!
siegert81 is offline   Reply With Quote
Old 2011-01-10, 07:17   #2
rajula
 
rajula's Avatar
 
"Tapio Rajala"
Feb 2010
Finland

32·5·7 Posts
Default

Quote:
Originally Posted by siegert81 View Post
If I wanted to find a factor of F20, what's the best program/approach?
The best approach is to use ECM. First look from http://mersenne.org/report_ECM/ where we are at with that and then start crunching away with GMP-ECM / Prime95.

Quote:
What if, instead, I wanted to find a factor of F200? F2000? F20000? F200000?
For F200 and maybe F2000 I would use GMP-Fermat and for the larger ones I would sieve with the appropriate program and then use pfgw. Some information is at http://www.fermatsearch.org/download.html.

Quote:
I began looking for proth primes of the form k*2^n+1 where 500,000<k<1,000,000 and n>20,000 (testing one n value at a time). So far, I've found dozens of primes, but none of them are Fermat factors.

I also began testing for 5,000,000<k<10,000,000 and n>8,000. I've found hundreds of primes at this level, but none of them are Fermat factors.

Do I need to just keep testing for much longer periods of time, or should I change my entire approach?
First of all, I recommend that you see from http://www.fermatsearch.org/stats/merge.php which ranges have been tested and which have been reserved for testing so that you are not redoing a range (if that is not your purpose). One possible way to join the search for the high n:s is to go to the PrimeGrip PRPNet Proth prime search -projects, see http://www.primegrid.com/forum_thread.php?id=3008.

Ask for more information if you wish. I am sure there are many here that are happy to help you.
rajula is offline   Reply With Quote
Old 2011-01-10, 18:50   #3
siegert81
 
Dec 2010

2·37 Posts
Default

I have pfgw, but the help file is not orderly. Is there a help file or a website that explains how to use pfgw?

As for the ranges I'm testing, I did look to make sure I'm covering virgin territory. I checked the fermatsearch site, and I also verified that no Fermat factors have been found in these ranges (yet).
siegert81 is offline   Reply With Quote
Old 2011-01-10, 21:39   #4
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102678 Posts
Default

Quote:
Originally Posted by siegert81 View Post
I have pfgw, but the help file is not orderly. Is there a help file or a website that explains how to use pfgw?
There are quite a few help files, but the most important are pfgwdoc.txt, telling you what switches do what, and abcfileformats.txt, which provides details on the ABC file formats, which are commonly used to give to PFGW for it to test.
TimSorbet is offline   Reply With Quote
Old 2011-01-11, 04:12   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by rajula View Post
For F200 and maybe F2000 I would use GMP-Fermat and for the larger ones I would sieve with the appropriate program and then use pfgw. Some information is at http://www.fermatsearch.org/download.html.
What is the algorithm that is being actually used to test out
whether k*2n+2+1 is a factor of 22[sup]n[/sup]+1 ?
for any specific, given value of k, for some particular value of that variable n.
Raman is offline   Reply With Quote
Old 2011-02-03, 09:34   #6
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

23·149 Posts
Default

Quote:
Originally Posted by Raman View Post
What is the algorithm that is being actually used to test out
whether k*2n+2+1 is a factor of 22[sup]n[/sup]+1 ?
for any specific, given value of k, for some particular value of that variable n.
As Far As I Know, first the k are seived to remove k candidates with 2^(n+2)+1 with small factors (maybee less than 30?). Then the remainder of 2^(2^n)+1 divided by k*2^(n+2)+1 is calculated. Since this number of digits in the Fermat number could be more than one billion and greater than available RAM, the number is loaded only a few bits at a time. In Binary, F(n) = 2^(2^n)+1 is a 1 followed by a long string of zeros and finally a one at the end. So, I imagine the computer performing long division like I learned in grade school and only remembering the temporary remainder. Every time, it checks if the remainder is one, or if it has gotten to the last digits of F(n). If k is not a factor, it chooses the next candidate for k, and does another long division. Or, I could be wrong.
MattcAnderson is offline   Reply With Quote
Old 2011-02-03, 11:10   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

110010010112 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
Or, I could be wrong.
Yes, totally wrong.
R. Gerbicz is offline   Reply With Quote
Old 2011-02-03, 12:24   #8
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Yes, totally wrong.
How does it work? Is it simply that Fn is calculated mod k*2n+2+1, or is there a more efficient algorithm? I can't find anything about it by googling.
TimSorbet is offline   Reply With Quote
Old 2011-02-03, 13:00   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32·179 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
How does it work? Is it simply that Fn is calculated mod k*2n+2+1, or is there a more efficient algorithm? I can't find anything about it by googling.
Yes, and in this case the mod operation is easy, because k is *small*. And in fact the code checks the smaller Fermat numbers also, because it is possible that k*2^(n+2)+1 is a divisor of F(n-1) or F(n-2),...

Last fiddled with by R. Gerbicz on 2011-02-03 at 13:00
R. Gerbicz is offline   Reply With Quote
Old 2011-02-03, 13:05   #10
rajula
 
rajula's Avatar
 
"Tapio Rajala"
Feb 2010
Finland

32×5×7 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
How does it work? Is it simply that Fn is calculated mod k*2n+2+1, or is there a more efficient algorithm? I can't find anything about it by googling.
One way to test all the possible Fermat numbers is to calculate (mod k*2n+2+1) first 22[SUP]0[/SUP]+1 and then continue to 22[SUP]1[/SUP]+1 and so on up to 22[SUP]n[/SUP]+1 by simply using the squaring 22[SUP]m+1[/SUP] = (22[SUP]m[/SUP])2. It seems that testing all the Fermat numbers is essentially as fast as testing only one.
rajula is offline   Reply With Quote
Old 2011-02-03, 13:08   #11
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Celebrate with one year since that factorization of number F14

What I meant was that

For example, 485*2338297+1 was proved to be prime by Souichi Murata in May 2007
but the fact that it divides with that Fermat number F338295 was only being revealed upon August 21, 2007.
(that is exactly ten years before that USA total solar eclipse)
Why is this delay? What is actually the algorithm that is being used up
for this purpose of verifying divisibility of some Fermat number?

Is it brute force - just simply testing divisibility - that is in some way similar to one that is
being used by GIMPS for some trial factoring cases?

Last fiddled with by Raman on 2011-02-03 at 13:34
Raman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What are the Primality Tests ( not factoring! ) for Fermat Numbers? Erasmus Math 46 2014-08-08 20:05
Elliptic Curve Method factoring - Fermat numbers philmoore Math 131 2006-12-18 06:27
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25
Factoring Smallest Fermat Numbers Erasmus Factoring 32 2004-02-27 11:41
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 07:52.


Thu Feb 2 07:52:58 UTC 2023 up 168 days, 5:21, 1 user, load averages: 0.92, 0.90, 0.85

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.

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