mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2003-06-04, 19:03   #1
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default Factoring Fermat Numbers

Hello all,

just out of mathematical interest, I did some research on Factoring Fermat Numbers and some site said that you can numbers F(n) with n<24 using Prime95.

I was just wondering how one would do that ? What's the worktodo.ini command for example ?

Greetings,
Axel Fox.
Axel Fox is offline   Reply With Quote
Old 2003-06-04, 19:16   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

25×5×7 Posts
Default Fermat number factoring

Take a look at this thread under "Math":

http://www.mersenneforum.org/viewtopic.php?t=109

Up through F24, ECM is probably the most useful factoring method right now for Fermat numbers, although P-1 factoring might be more effective on F25 and F26. The status page is at:

http://www.mersenne.org/ecmf.htm

The work listed there includes some effort by individuals using programs other than Prime95/mprime, notably Richard Crandall's C program. The last factor found by ECM was the 23-digit factor of F18 found in April 1999 by McIntosh and Tardif using Crandall's program, and my opinion is that we are overdue for a new discovery!
philmoore is offline   Reply With Quote
Old 2003-06-04, 19:31   #3
Axel Fox
 
Axel Fox's Avatar
 
May 2003

6016 Posts
Default

Thank you very much for providing me this link.
Axel Fox is offline   Reply With Quote
Old 2003-06-04, 19:39   #4
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

What about running P-1 on fermat numbers. Is it also more efficient to factor 2^(2N)-1?
smh is offline   Reply With Quote
Old 2003-06-04, 19:50   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100011000002 Posts
Default

You could experiment. On a Pentium-4, it very well might be faster doing P-1 on M67108864 than on P33554432 because the SSE2 optimizations are only implemented in the M-number code. I have discovered that running ECM on P-numbers is more efficient on Pentium-3 and Athlon-XP chips than on Pentium-4 machines, so my guess is that a fast Athlon might be the best machine for doing P-1 on F25 and F26, and in fact a 2GHz Athlon would probably run faster on P33554432 than a 2GHz Pentium-4 would on M67108864. Keep in mind that at these FFT sizes, memory availability is also an issue.
philmoore is offline   Reply With Quote
Old 2003-06-04, 20:43   #6
Axel Fox
 
Axel Fox's Avatar
 
May 2003

1408 Posts
Default

Another question. I'm experimenting a little bit with ECM on M8388608.
This enables me to find possible divisors for F22, F21, F20, ...

Will the program tell me when I find a factor of one of these Fermat numbers or will is just say "M8388608 has a factor : XXXXXXXX" ?

Axel Fox.
Axel Fox is offline   Reply With Quote
Old 2003-06-04, 20:51   #7
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22×43×47 Posts
Default

Quote:
Originally Posted by Axel Fox
Will the program tell me when I find a factor of one of these Fermat numbers or will is just say "M8388608 has a factor : XXXXXXXX" ?
It will just say M8388608 has a factor: xxxx

Then the fun begins - finding which F number you've cracked!
Prime95 is offline   Reply With Quote
Old 2003-06-04, 21:08   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

25·5·7 Posts
Default identifying factors

The program will just say something like:

ECM found a factor in curve #1, stage #2
Sigma=2049756470223819, B1=44000000, B2=4290000000.
M32768 has a factor: 4659775785220018543264560743076778192897

(Actually, it will write this in the results.txt file, but also write something similar in the dialogue box.) Therefore, if you find a factor, you will have the problem of determining which Fermat number your factor actually belongs to. I can figure this out by starting with 2 and successively squaring modulo the factor:

2^2 mod (factor) = 4
4^2 mod (factor) = 16, etc.
After 10 successive squarings, I get that
2^(2^10) mod 4659775785220018543264560743076778192897 = 4659775785220018543264560743076778192896,
that is, this factor divides F10 = 2^(2^10) + 1. (This factor only turned up because I had deleted it from the lowm.txt file.) If I square the result one more time, I of course will find out that 2^(2^11) mod (factor) = 1. (Use your favorite large integer calculation package for this.)
philmoore is offline   Reply With Quote
Old 2003-06-04, 22:32   #9
Axel Fox
 
Axel Fox's Avatar
 
May 2003

6016 Posts
Default

How do you mean, "This factor only turned up because I deleted it from the lowm.txt file." ? Do you have to put the lowm.txt file in the Prime95 directory ? And then it doesn't report factors already in there, or what ?
Axel Fox is offline   Reply With Quote
Old 2003-06-04, 22:40   #10
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100011000002 Posts
Default

That is correct. If you have already started a curve, it is not too late. Download lowm.txt into the Prime95 directory, and perhaps you also need to stop and restart the program, I am not completely sure. Otherwise, the program will report a factor at the end of stage 1 which will be the product of several of the known factors.
philmoore is offline   Reply With Quote
Old 2003-06-04, 23:24   #11
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

Hmm, another question.

Since it seems to be possible that ECM gives you a composite factor, suppose I find a really large factor some day, how do I check wether the factor is a prime factor or a composite one ?

PS : Sorry if my stupid questions are boring you.
Axel Fox 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
Factoring Fermat numbers siegert81 Factoring 12 2011-02-03 13:55
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

All times are UTC. The time now is 20:38.


Fri Dec 2 20:38:12 UTC 2022 up 106 days, 18:06, 0 users, load averages: 1.30, 1.19, 1.17

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

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