mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-02-16, 15:50   #1
Erasmus
 
Feb 2004

101112 Posts
Default Factoring Smallest Fermat Numbers

Hi,

I was searching for some specialised factorization websites and found out that some relatively small Fermat numbers remain unfactored for 40 years.

INFO Fermat Numbers are of the form (2^N) + 1 where N is also a power of 2 ( not necessarily the exponent is prime unlike Mersenne )

If internet researches are up to date, F14 which is 4933 digits long has no known factors. Also, F20, F22, F24 is unfactored but they are slightly longer than F14 ( F20 is 315000 digits !! )

Anyway, these four Fermat numbers are proven to be composite, interesting thing is that F14 was proven composite in 1963, but there were no wondrous man searching for its factors.

My problem starts here, i am very bad at programming and computing skills, so i have doubt using giantint program to search for fermat factors.

any of you know some info about programs skilled specifically for factoring fermat numbers? I have proth and searching for generalised fermat right now, but i couldn't make it search for original fermat numbers. Is there a way to test F14 with Proth.EXE ???????

Thanks for your help and also if there is a GUI based fermat search program, i will appreciate...
Erasmus is offline   Reply With Quote
Old 2004-02-16, 16:38   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22×3×401 Posts
Default

I will post a copy of Durman's Feramt.exe as soon as I get home.

Luigi
ET_ is offline   Reply With Quote
Old 2004-02-16, 18:50   #3
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

52·17 Posts
Default

I have used Prime95 to try finding factors of Fermat numbers. I don't know how it compares to other programs.

If you have a Pentium 4 computer Prime95 is very fast on 2^N-1 ECM factoring. Then it is actually faster to test e.g. M262144 = 2^262144-1 than F17 = 2^131072+1, which you can do since M262144 = F17*F16*F15*...*F0.

Link: http://www.mersenne.org/ecm.htm and continue with the "Fermat numbers" link at the bottom of that page.
patrik is offline   Reply With Quote
Old 2004-02-16, 19:36   #4
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22×3×401 Posts
Default

Quote:
Originally Posted by ET_
I will post a copy of Durman's Feramt.exe as soon as I get home.

Luigi
Whops! The upload is limited to 100 KB while the file is 288 KB.

PM me your email address and I'll send you the program!

Luigi
ET_ is offline   Reply With Quote
Old 2004-02-16, 21:27   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts
Default

I think that Prime95 is currently the best available program for trying to factor the lowest Fermat numbers F12 through F26 by the elliptic curve method (ECM), although Alex Kruppa has suggested to me that it may actually be more efficient to factor F12 and maybe even F13 by running the first stage with Prime95 and the second stage with GMP-ECM. As Patrik has pointed out, you may use Prime95 to either run curves on a single Fermat number, or you can run on several Fermat numbers simultaneously. So for example, to run curves on F14, you can input your number as P16384 (= 2^(2^14) + 1), or you can run curves on M32768 (= 2^(2^15) - 1). The latter option will also look for factors of all the lower Fermat numbers as well, so it could conceivably find new factors of F12, F13, or F14 (the lower Fermat numbers have already been completely factored.) I call these two modes P-mode and M-mode. P-mode does not run well on Pentium-4's, as the P-mode multiplication routines have not incorporated SSE2 code. So if you have a Pentium-4, you will want to run in M-mode. If you have an AMD Athlon or a Pentium-3 based system, either mode works well, although even for these systems, M-mode is slightly more efficient. But if you want to concentrate on one particular Fermat number like F14, and you have a Pentium-3 or Athlon, you will want to run in P-mode.

ECM and P-1 factoring are probably the best methods for trying to factor the Fermat numbers up through F24 or so. But above this, ECM requires large amounts of memory, and trial factoring takes over as the best method. Leonid Durman's Fermat.exe program is a good trial factoring program for Fermat numbers up through F1000 or so.
philmoore is offline   Reply With Quote
Old 2004-02-17, 00:30   #6
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

Leonid Durman's Fermat.exe can be downloaded off the following page

http://web.archive.org/web/200306212...matsearch.org/

the downloaded file is packFermat.exe, it is really a self-extracting zip file containing Fermat.exe, Whatnew.eng, Whatnew.rus

When I downloaded it the last byte was cutoff (with a value 0) you will need a program to fix the zip file, such as pkzipfix, or any other that can extract a file from a minimally damaged zip file.

If you have frhed, free hex editor you can just add a byte with the value 0 to the end of the file and save.
dsouza123 is offline   Reply With Quote
Old 2004-02-17, 07:53   #7
Erasmus
 
Feb 2004

23 Posts
Default Factoring Fermats

Really thanks for your interest on this subject,

I have a P4, so i think it will be better using M-mode for 2^14, but i have 2nd pack of questions now!

1- F14 is a very small number when compared to other numbers being tested in all projects, why anybody did not come up with a factorization?

2- I will first use ECM of Prime95 with M32768, i was not sure about parameters used, so here is what i entered :
B1 : 1 000 000
B2 : 2 900 000
# of curves : 100

After these instructions, prime95 started to iterate like this way :
...
...
[Feb 17 ...] At Prime 82279 Time thus far...
[Feb 17 ...] At Prime 82301 Time thus far...
...
...

And it is growing. Am i doing right for this exponent or is there an optimal set of instructions for finding the factors?

3- If there is some optimal set of instructions, how do they change for F17,F20,F22 ?

OR is there a limiting equation to calculate # of curves needed, bounds etc. for a specific exponent???


Thanks for all your help
Erasmus is offline   Reply With Quote
Old 2004-02-17, 11:39   #8
nfortino
 
nfortino's Avatar
 
Nov 2003

3×5×11 Posts
Default

Quote:
Originally Posted by Erasmus
OR is there a limiting equation to calculate # of curves needed, bounds etc. for a specific exponent???
You should follow the instructions at http://mersenne.org/ecm.htm. If you are factoring Fermat numbers, follow the Fermat status page link at the bottom of the page to see the status of the numbers you are interested in. If you are using M-mode to factor F14, F13 and F12, you probably want to use a B1 of 44,000,000. These curves will probably take a long time. If you are impatient, you could factor F14 directly with a B1 of 11,000,000, trading efficiency for psychological gain. Note that it would be even more inefficient to factor M32768, since the status page says both F13 and F12 have been finished up to that bound, making it very improbable that you will find a factor. Finally, I beleive that the factoring project uses the standard B2=100*B1.
nfortino is offline   Reply With Quote
Old 2004-02-17, 17:26   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

246358 Posts
Default

Quote:
Originally Posted by Erasmus
1- F14 is a very small number when compared to other numbers being tested in all projects, why anybody did not come up with a factorization?

Thanks for all your help
Because F14 is a very large number. It is over 16 thousand bits long. State of the art in factoring general numbers is currently 576 bits, and it's only just over 800 bits for numbers which can be treated by the Special Number Field Sieve. The NFSNET project is currently working on an integer which is larger than any which has so far been factored. That integer has 811 bits.


Paul
xilman is offline   Reply With Quote
Old 2004-02-17, 22:34   #10
Erasmus
 
Feb 2004

23 Posts
Default

Sure F14 is still a huge number with 4933 digits. But check the status of some fermat numbers ( F2478782 , http://www.prothsearch.net/fermat.html )
Its factor is with k=3 n=2478785

Of course factoring ordinary numbers are easy but i'm still surprised about F14 remaining with any factor known. Check the above URL to see more than 250 known factors for various Fermat numbers.

Anyway, i am trying hard with the help of philmoore, started ECM on Prime95 with B1=11000000, i wish i will come up with brand new factors!!!

ONE LAST QUESTION : What is the logic of running multiple curves ( e.g 10 curves with B1=11000000 ) without changing B1, won't it give the same results with previous curve???????
Erasmus is offline   Reply With Quote
Old 2004-02-17, 23:19   #11
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts
Default

Notice that each time the program begins a new curve, it prints out a line like:
ECM on M32768: curve #7 with s=46930544369504, B1=11000000, B2=1100000000
The s value is chosen by a random number generator. Different values of s define different elliptic curves to use in the calculation. We don't know which values of s will find factors, but we try several hundred or several thousand curves, hoping that we will get lucky!

By the way, an elliptic curve can be thought of a structure on the set of all solutions to an equation of the form:
y^2 = x^3 + A*x^2 + B*x
Different choices of s lead to different coefficients A and B. I wrote a rough non-technical description of the algorithm in the Math thread under "Elliptic Curve Method - the theory":
http://www.mersenneforum.org/showthread.php?t=194
philmoore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors UberNumberGeek Factoring 51 2017-02-13 20:30
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
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57

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

Fri Apr 23 15:08:42 UTC 2021 up 15 days, 9:49, 0 users, load averages: 1.62, 1.98, 2.11

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