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 :
Post a Comment