Program to factor F14

[dsouza123]

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.

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

[philmoore]

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!

[dsouza123]

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.

[Xyzzy]

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

I mean, even though 10⁵⁰ years is a lot less than 10⁵⁶ years, it still seems like a long time to me... (Or am I missing something?)

[dsouza123]

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.

[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/

[philmoore]

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!)

[Carlos]

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

[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

[xilman]

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

[Xyzzy]

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!)