[jnkmswd] Parallelizable verification of the compositeness of the twenty-fourth Fermat number

The initial computation of Pepin's Test testing the primality of a Fermat number is an inherently serial computation.  However, a subsequent verification can be done in a parallelizable computation if many intermediate snapshots of the initial computation are available.

The snapshots are like links in a chain.  To verify the integrity of the chain, verify that each link correctly connects to the next.  These verification computations can be done in parallel.

We present a verification of the compositeness of 24th Fermat number, F24 = 2^2^24+1, a 5050446-digit number, replicating the computation originally published in "The twenty-fourth Fermat number is composite" by Richard E. Crandall, Ernst W. Mayer, and Jason S. Papadopoulos in 2003.  (However, http://www.prothsearch.com/fermat.html gives the date as 1999.)  Crandall, et al., did not publish intermediate snapshots of the computation.  We do so here.

The intermediate results are in text format (compressed with bzip2) for ease of understanding.  All numbers are in base 10.  The format of the intermediate results are as follows:

3^2^0 mod F24 = 3
3^2^479349 mod F24 = ...
3^2^958698 mod F24 = ...
...
3^2^16777215 mod F24 = ...

Each line has a 5-million digit intermediate result to the right of the equals sign, where the ellipses are above.  We provide the snapshots every 479349 squarings, for 35 snapshots in total.  We also provide in the text file some comments (prefixed with #), including a few finer-grained early intermediate results with middle digits elided to help with initial testing of a future verification run.  F20 may also be useful for testing.

The 35 snapshots allow a future verification run to be done with 35-way parallelization.  With current hardware (e.g., the hardware that generated these results), each intermediate result takes about 2 days to compute.  If you have 35 cores available, F24 can therefore be verified composite in 2 wall-clock days, much less than the 70 wall-clock days that would be required if you didn't have snapshots.  We expect computers to become faster in the future, bringing 2 days to even less.  In the absence of a small factor being discovered, this is might be fastest way to verify the compositeness of F24.

The final residue, that of 3^2^16777215 mod F24, agrees with the remainders published by Crandall, et al.  Incidentally, verification in parallel is essentially identical to the "wavefront" technique described in the paper.  The only difference is that we publish the intermediate results so that they can be independently verified.

We actually calculated intermediate results every 53261 squarings for 315 total snapshots, but we lack the 640 MB of permanent web space necessary to publish them.  (We took advantage of 2^24-1 = 16777215 having many divisors, including 479349 and 53261.)  Also, as computers become faster, we expect that having so many intermediate results will become less useful and more a waste of disk.

Just for fun, we have inserted the 315 snapshots (640 MB) into Freenet at the following address:

CHK@FDC-tl4BX3Pz7yMZDzhPBhDhyx0TWiSLRi-lN0ikCSk,SIB9iSpmFl54-FCBUbfG0ftfoW25NOK4WJGy~Yo66QY,AAMC--8/fermat24-all.txt.bz2