Fermat cofactors

[kriesel]

Originally Posted by cxc

for the forward half only the new unreleased version of mlucas that Ernst had been using seems to be capable of running the Pépin test on Fermats F₃₁ and beyond.

What's missing from already-released Mlucas, in your view?
As I understand it, what's unreleased is the PRP-proof-generation capability, & for checking cofactors, unsupported "fast Suyama-style cofactor-PRP test". The latter may only be unsupported for Mersennes in Mlucas, since Ernst makes reference to running them on F25-F29 in Mlucas in 2018 https://mersenneforum.org/showpost.p...3&postcount=82.

F31-F33 should theoretically be within the Pepin test range of Mlucas expanded to up to 512M fft length in v20.1.1 which has been available for over a year in its 06-Jul 2022 patched form, and in earlier patch levels and in V20.1 before that. https://mersenneforum.org/showpost.p...47&postcount=1
https://mersenneforum.org/showpost.p...postcount=2060
https://mersenneforum.org/showpost.p...postcount=2064
Ernst had been running both-stages P-1 on F33 for at least a year. https://mersenneforum.org/showpost.p...47&postcount=1
I haven't seen posted a conclusion to that large P-1 run yet, of order 2 years overall.

A big impediment to Pepin testing F31-F33 is run time projected on available CPUs, until the adaptation of the Pepin test into Gpuowl & a really fast GPU occurs as described in the last paragraph of https://mersenneforum.org/showpost.p...51&postcount=6. I roughly estimate potential F3x Pe'pin test run time based on gpuowl Mersenne PRP performance here:
Benchmarked Radeon VII Mersenne iteration rate corresponds to 2172.3M exponent 620 days per PRP, & scaling ~ O(p^2.1) at large exponent. Extrapolating to Pe'pin testing Fermat numbers on similar speed hardware and software, if & when available,
F30 2^1073741824 + 1; ~ 141 days or 4.6 months
F31 2^2147483648 + 1; ~ 605 days or 1.7 years
F32 2^4294967296 + 1; ~ 2595 days or 7.1 years
F33 2^8589934592 + 1; ~ 11127 days or 30.5 years
There are currently server-farm-grade GPUs capable of more than triple the DP speed of the Radeon VII. See the online GPU benchmarks, so Pepin testing F33 might be possible at ~10 years duration on currently existing hardware after additional substantial software development.

Ernst's health issues had slowed and now apparently stopped Mlucas development & other involvement.
His last forum post was nearly 3 months ago. https://mersenneforum.org/showpost.p...postcount=2934
His hardware continues to contribute Mersenne PRP/proof results from gpuowl, probably automatically via a primenet.py script, as recently as today, and occasional GIMPS LL DC wavefront results by Mlucas from "nuc2", most recently 2023-07-24.

But I don't see any reference to suyama in the Mlucas help.txt. https://www.mersenneforum.org/mayer/README.html contains documentation of how to use for Mersenne numbers but not for Fermat numbers.
If the available functionality is to be used in existing released Mlucas, some analysis of the source code is likely to be necessary.

Excerpted from the Mlucas v20.1.1 help.txt:

 -f {int}
	Performs a base-3 Pe'pin test on the Fermat number F(num) = 2^(2^num) + 1.
	If desired this can be invoked together with the -fft option, as for the Mersenne-number
	self-tests (see notes about the -m flag). Note that not all FFT lengths supported for -m
	are available for -f; the supported ones are of form k × 2^n, where k is an odd integer
	in the set [1,7,15,63].

	Optimal radix sets and timings are written to a fermat.cfg file.
	Performs as many iterations as specified via the -iters flag [required].

======================

[6]: Residue shift:

 -shift {int}
	Number of bits by which to shift the initial seed (= iteration-0 residue). This initial
	shift count is doubled (modulo the binary exponent of the modulus being tested) each
	iteration; for Fermat-number tests the mod-doubling is further augmented by addition of a
	random bit, in order to keep the shift count from landing on 0 after (Fermat-number index)
	iterations and remaining 0. (Cf. https://mersenneforum.org/showthread.php?p=582525#post582525)

	Savefile residues are rightward-shifted by the current shift count
	before being written to the file; thus savefiles contain the unshifted residue, and
	separately the current shift count, which the program uses to leftward-shift the
	savefile residue when the program is restarted from interrupt.

	The shift count is a 32-bit unsigned int; any modulus having > 2^32 bits (thus using an
	FFT length of 256M or larger) requires 0 shift.

======================

[7]: Probable-primality testing mode:

 -prp {int}
	Instead of running the rigorous primality test defined for the modulus type
	in question (Lucas-Lehmer test for Mersenne numbers, Pe'pin test for Fermat numbers),
	do a probable-primality test to the specified integer base b = {int}.

	For a Mersenne number M(p), starting with initial seed x = b (which must not = 2
	or a power of 2), this means do a Fermat-PRP test, consisting of (p-2) iterations of
	form x = b*x^2 (mod M(p)) plus a final mod-squaring x = x^2 (mod M(p)), with M(p) being
	a probable-prime to base b if the result == 1.

	For a Fermat number F(m), starting with initial seed x = b (which must not = 2
	or a power of 2), this means do an Euler-PRP test (referred to as a Pe'pin test for these
	moduli), i.e. do 2^m-1 iterations of form x = b*x^2 (mod F(m)), with F(m) being not merely
	a probable prime but in fact deterministically a prime if the result == -1. The reason we
	still use the -prp flag in the Fermat case is for legacy-code compatibility: All pre-v18
	Mlucas versions supported only Pe'pin testing to base b = 3; now the user can use the -prp
	flag with a suitable base-value to override this default choice of base.

[mathwiz]

Originally Posted by cxc

That only leaves F₂₉ = 2^536870912 + 1, and F₃₀ = 2^1073741824 + 1 to be verified: first a PRP proof generated by mprime, then running the Suyama cofactor test using cofact (each utilises the gwnum library for all that modular squaring). I don’t think Gary is intending to run F₂₉ immediately, as it would be a multi-month run; and as for F₃₀, that is a monster run and would require the box running the test to have the AVX-512 extensions for mprime to deal with such a large exponent.

Here goes nothing!

[Main thread Aug 18 17:52] Mersenne number primality test program version 30.14
[Main thread Aug 18 17:52] Optimizing for CPU architecture: Core i3/i5/i7, L2 cache size: 32x1 MB, L3 cache size: 39424 KB
[Main thread Aug 18 17:52] Starting worker.
...
[Worker Aug 18 17:52] Starting Gerbicz error-checking PRP test of F29/2405286912458753 using all-complex AVX-512 FFT length 30M, Pass1=1280, Pass2=24K, clm=2, 32 threads
[Worker Aug 18 17:52] Preallocating disk space for the proof interim residues file p536870912.residues
[Worker Aug 18 17:53] PRP proof using power=6x2 and 64-bit hash size.
[Worker Aug 18 17:53] Proof requires 4.3GB of temporary disk space and uploading a 940MB proof file.
[Worker Aug 18 17:55] Iteration: 10000 / 536870912 [0.00%], ms/iter: 12.773, ETA: 79d 08:53
[Worker Aug 18 17:57] Iteration: 20000 / 536870912 [0.00%], ms/iter: 12.388, ETA: 76d 23:24
[Worker Aug 18 17:59] Iteration: 30000 / 536870912 [0.00%], ms/iter: 12.366, ETA: 76d 19:59

Hope I can keep it going until November.

[kriesel]

Originally Posted by mathwiz

Here goes nothing!
...

Hope I can keep it going until November.

That would be a good shakedown cruise for doing F30 in ~11 months on the same hardware. Back up frequently, & good luck!

[Gary]

Originally Posted by mathwiz

Here goes nothing!
...
Hope I can keep it going until November.

Thanks mathwiz! Since you are running F29, I'll keep runnng GIMPS stuff on my computer instead of running F29 for 4 months! When mprime finishes and you run cofact, if you have any problems just let me know.

Originally Posted by kriesel

What's missing from already-released Mlucas, in your view?
As I understand it, what's unreleased is the PRP-proof-generation capability, & for checking cofactors, unsupported "fast Suyama-style cofactor-PRP test".

That matches my understanding also. In https://www.mersenneforum.org/showpo...3&postcount=82 Ernst said "In the context of testing the cofactor-PRP functionality which will be supported in Mlucas v21, I've at long last done Suyama-style PRP tests on the cofactors of F25-F30, using the Pépin-test residues I've generated for same over the past 10 years...". So it sounds like the first version of Mlucas to support the Suyama cofactor test is v21. He might not want to release v21 if there is a lot of other new functionality in it that is not sufficiently tested. So if v20.1 can generate and save the Pepin residue in a documented format for F31 and higher, I could write a cofact-style program to complete the Suyama steps.

[cxc]

Best of luck, mathwiz, from me also! When the PRP run is just about complete, you’ll want to turn on:
InterimResidues=1
in prime.txt, as the Pépin and Suyama A residues should be the final two residues generated by mprime, for which Ernst reported values BECE1E5FFBE5EC12 and 9BD416DB3918C152 respectively.

This was George’s advice in the mprime 30.14 software thread a day or so back; once my own run concludes I’ll post an update if mprime behaved nicely and gave me a couple of matching values to Ernst’s.

Brevity was the enemy of precision in my previous post on the previous page: I should have said, the only capable piece of software today for running the Pépin test on F₃₁, F₃₂, and F₃₃ with the features we want is the un-released mlucas, for those two reasons you’ve all been discussing: proof generation, and having the Suyama test code following directly on. (P–1 factorisation on the other hand, you don’t need those features.)

You don’t want to run such an expensive computation as the Pépin test every time a factor turns up, just to be able to run the Suyama test on the cofactor, and the VDF proof format seems as portable a solution for storing the full residue needed for the test. The Suyama A value never changes; you get a different Suyama B value depending on which factor(s) you test, but this is the relatively easy and cheap value to compute (though it still has to be calculated modulo F_m).

[cxc]

I was hoping to post this before the end of August but there were a few delays!
Turning on InterimResidues=1 in mprime’s prime.txt yielded the Pépin residue mod 2⁶⁴ immediately before mprime generated the proof file. The numbering of residues is a little haphazard owing to Gerbicz error checking, but these values did occur in the correct order in spite of that!

[Worker Sep 2 00:55:48] F27/151413703311361/231292694251438081 interim PRP residue 043A6C8B9272B297 at iteration 134217727
[Worker Sep 2 01:02:17] F27/151413703311361/231292694251438081 interim PRP residue C3B191C45CCD7820 at iteration 134217685

And from cofact, all of these are in agreement with Ernst Mayer and Gary Gostin:

Testing the F27 cofactor for primality using the following known factors: 151413703311361 231292694251438081
Cofactor is 40403531 digits long
Suyama A residue mod 2^64 2^36 2^36-1 2^35-1: 0xC3B191C45CCD7820 18736838688 55240256170 21887650168 (decimal)
Suyama B residue mod 2^64 2^36 2^36-1 2^35-1: 0x485F292142F953EC 5418603500 26481669619 20036545122 (decimal)
(A-B) mod C residue mod 2^64 2^36 2^36-1 2^35-1: 0x79E89190C56372B7 3311628983 29330680430 2608954171 (decimal)
GCD (A-B, C) = 1
F27 cofactor is composite, and is not a prime power