Saturday, September 15, 2018

[rufudqzr] Verifying the compositeness of the 20th Fermat number

Pari/GP:

? ispseudoprime(2^2^20+1)
time = 12h, 17min, 47,643 ms.
%1 = 0

In 1987, this computation took 10 CPU days on a Cray 2 supercomputer, verified in 3.4 CPU days on a Cray X-MP, earning a journal publication for its authors ("The twentieth Fermat number is composite").  It's doable now on a personal computer without special-purpose software, but it's still not trivial to do.

This still remains the only way to demonstrate the compositeness of F20; still no small factors have been discovered in the years since.

The future looks bright for future speedups of this computation.  Multiplying million-bit numbers seems like something that GPU-accelerated FFT could do well on, but GPU-accelerated arbitrary precision arithmetic has not yet made its way into general-purpose software like GNU MP and Pari/GP.

Update: another attempt.

No comments :