mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2004-02-28, 00:30   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default Program to factor F14

I have written a program to find the smallest factor of F14.

F14 is the fourteenth fermat number, 2^(2^14) + 1.
Given m = 14, n = m+2 = 16,
each factor of F14 is in the form k*2^n + 1 = k*2^16 + 1 = k * 65536 + 1.
with k an integer in the range 1..2^240-1.

F14 is the smallest composite fermat number without a known factor.
It is determined to be composite by

There is a conjecture that the smallest factor of Fermat numbers is less than
2^(16*n) = 2^(16*16) = 2^256.

Code:
Pseudo code is.

f = 1
b = 65536
for k = 1 to 2^240 - 1 do
  f = k * b + 1
  if (f14 mod f) = 0 then
    write( f is a factor of F14 )
    exitfor
  endif
endfor

better pseudo code 

factor_found = FALSE
f = 65536 + 1
while (f < 2^256) and (factor_found = FALSE) do
  if isprime(f) then
     ans = f14 mod f
     if (ans = 0) then
       factor_found = TRUE
       write( f )
     endif
  endif
  f = f + 65536
endwhile
dsouza123 is offline   Reply With Quote
Old 2004-02-28, 19:05   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

25·5·7 Posts
Default

This pseudo-code certainly seems to work logically. In actual practice, rather than performing the isprime(f) calculation, the program can be optimized by sieving out f divisible by small primes and doing the f14 mod f calculation on any f remaining after sieving - the programs written by Leonid Durman (fermat.exe) and Tony Forbes (MFAC) do this. Even if optimized and run on a fast PC, I estimate that the program will have to run around 10^24 years before it is even checking possible factors that might have been missed by the Elliptic Curve Method, and if it doesn't find a factor, it will have to run around 10^56 years before it reaches k = 2^240 and stops. If you translate this pseudo-code into an actual program, I hope you have a lot of patience!
philmoore is offline   Reply With Quote
Old 2004-02-28, 21:44   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

Any other ways to optimize, other programs that are tackling the problem ?

Doing the sieve before hand and modding what is left is probably
equivalent to doing the prime test just when needed.
It requires less space doing it just when needed, no need to hold all the
values remain.

Running it with random starting points (values of at least 2^208) will
test numbers beyond the typical ECM ranges so not duplicate ECM efforts.

The items that optimization by algorithm or code tweaks could help:
The mod function, many different algorithms and code tweaks available largest amount of time to be saved.
The isprime function, straight forward no obvious optimizations.
The increment function, not much to optimize.

The language/compiler can make a difference, I wrote a version in delphi 4
as a console (text mode) program, in C or Assembly it may be quicker.
If the compiler supports any of the SIMD instructions MMX,3DNow,SSE/SSE2
there could be some gain in speed.
dsouza123 is offline   Reply With Quote
Old 2004-02-29, 15:15   #4
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

2×17×251 Posts
Default

Even if you made it a million times faster wouldn't it still take a super long time to run?

I mean, even though 1050 years is a lot less than 1056 years, it still seems like a long time to me... (Or am I missing something?)
Xyzzy is offline   Reply With Quote
Old 2004-03-01, 01:15   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

ECM factoring uses random curves and would take decades to check
just the 50 digit numbers, factoring random values closer to the 77 digit limit
could find the small factor of F14.

Making it as efficient as possible is desirable just as it is for Prime95, with all the optimizations both algorithmic ( sieving, mod 8, small prime tests ) and coding ( assembly ) Prime95 has become incredibly fast at trial factoring, using DWT to do multiplication has eliminated doing mods in LL.

An exhaustive search by trial factoring of F14 is unrealistic but tests from random
starting points for some fixed amount of iterations, might find it in some
resonable amount of time.
dsouza123 is offline   Reply With Quote
Old 2004-03-01, 02:30   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5×29×47 Posts
Default

Last year, I had written a GMP based program to find factors to Fermat numbers. It is as fast as Leonid's fermat.exe on some CPUs and faster on others. It can be compiled and run on any CPU. You can find the source at:

http://groups.yahoo.com/group/Fermat...es/GMP-Fermat/
rogue is online now   Reply With Quote
Old 2004-03-01, 19:58   #7
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

46016 Posts
Default

quote:

"ECM factoring uses random curves and would take decades to check
just the 50 digit numbers, factoring random values closer to the 77 digit limit
could find the small factor of F14."

My estimate of 16 years or so is still much more hopeful than the 10^29 years it would take to find 50-digit factors by trial factoring. 70-digit factors are a big jump, but I still estimate that a project the size of GIMPS could find any 70-digit factors in less than a year. Sure, you might be phenomenally lucky and just happen to pick the right range, but you might get lucky and find that factor on the very first curve also.

(Of course, it is hard to imagine 30,000 people getting as excited over finding a 70-digit factor as over finding a record-sized prime, but that's a different matter. At least we are fairly certain another Mersenne prime will show up sooner or later, but there is no guarantee that F14 has a factor of less than 77 digits!)
philmoore is offline   Reply With Quote
Old 2005-09-11, 13:35   #8
Carlos
 
Carlos's Avatar
 
Jan 2005

13 Posts
Angry Fermat's method of factoring program using GMP

Quote:
Originally Posted by rogue
Last year, I had written a GMP based program to find factors to Fermat numbers. It is as fast as Leonid's fermat.exe on some CPUs and faster on others. It can be compiled and run on any CPU. You can find the source at:

http://groups.yahoo.com/group/Fermat...es/GMP-Fermat/
I have tried to download your program from Yahoo Groups but I need to be a member of FermatNumbers! How do I download your program?

Thank you
Carlos
Carlos is offline   Reply With Quote
Old 2005-09-11, 15:28   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

>I have tried to download your program from Yahoo Groups but I need to be a member
>of FermatNumbers! How do I download your program?

Become a member of FermatNumbers?

Alex

Last fiddled with by akruppa on 2005-09-11 at 15:29
akruppa is offline   Reply With Quote
Old 2005-09-11, 18:20   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1157710 Posts
Default

Quote:
Originally Posted by akruppa
>I have tried to download your program from Yahoo Groups but I need to be a member
>of FermatNumbers! How do I download your program?

Become a member of FermatNumbers?

Alex
Nice!

You should be given an award for your skill in stating the bleeding obvious

Paul
xilman is offline   Reply With Quote
Old 2005-09-11, 22:31   #11
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

2×17×251 Posts
Default

If you email me the binary I can attach it to this forum... Or you could upload it to the wiki...

(I hate sites that you have to join to access files and stuff!)

Xyzzy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
My factor program... Xyzzy Programming 18 2014-07-26 15:42
New program to fully factor with GMP-ECM rogue GMP-ECM 51 2009-06-01 12:53
C program to factor using GMP-ECM and msieve lazy GMP-ECM 6 2007-06-16 18:12
Where I find the best program to it factor keys? I use AMD. chrow Factoring 5 2004-02-19 10:15
New program to test a single factor dsouza123 Programming 6 2004-01-13 03:53

All times are UTC. The time now is 03:00.


Wed Nov 30 03:00:03 UTC 2022 up 104 days, 28 mins, 0 users, load averages: 0.94, 0.81, 0.78

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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”