Again seemingly a problem for the Fermats; Mlucas 21 now has cofactor testing, where either a Mersenne or Fermat number with known factors is PRP tested for compositeness of the cofactor. This is achieved by doing a 3-PRP test of the large number, then exponentiating 3 by the product of known factors – 1, and subtracting the two results modulo the cofactor:
P = Q · C, where P = the Mersenne or Fermat number; Q = p1·p2·…·pi is product of known factors, and C is the cofactor;
A = 3P–1 (mod P);
B = 3Q–1 (mod P); and by Fermat’s little theorem,
A – B (mod C) should be non-zero if C is composite; otherwise C is probably prime to the base 3Q.
The issue with the Fermat numbers is that the A result is difficult to obtain (Ernst spent 5 years chasing the result for F30) so the worktodo line
Fermat,Test=30
should save the final residue of the Pépin test, which is 3½(F30–1) (mod F30), which is exactly one modular squaring before obtaining the A value.
This does not seem to be happening with the Pépin test. Instead when the PRP test completes the Res64 modulo 264 residue is written to stdout and the .stat file, but the full residue is not saved, preventing the cofactor test.
Edited to add: there is a rather hacky workaround to generate the final residue, but it would be preferable not to have to resort to using anything so crude; and indeed there are other superior methods.
The same seems to be true of Mersenne numbers, however the cofactor code fortunately runs correctly and immediately after the primality test as there is only one worktodo entry, and so it does not need to “restart”; e.g. having added a worktodo entry of
[2024-02-29 10:22:08] M1063427 Iter# = 1063427 [100.00% complete] clocks = 00:00:02.517 [ 0.7346 msec/iter] Res64: DC727AB157FD5B77. AvgMaxErr = 0.162886046. MaxErr = 0.281250000. Residue shift count = 639848.
Suyama-PRP on cofactors of M1063427: using FFT length 52K = 53248 8-byte floats.
p1063427.G this gives an average 19.971210186298077 bits per digit
Fermat-PRP residue (A) = **0x34F046857B8DEDB7**,140702053821552, 4314796808
Processed 158 bits in binary modpow; MaxErr = 0.281250000
3^(F-1) residue (B) = 0x6EDA90980BA1A104,20717759102, 8128775763
(A - B) Res64 = 0xC615B5ED6FEC4CB3, C Res64 = 0xC893A566EEE74777
(A - B)/C: Quotient = 61782895853496272969963902813274391688714652455, Remainder Res64 = 0x32E74AF916FA4C92
Suyama Cofactor-PRP test of M1063427 / 68506830638546017 / 9191962833192559119894251405401 with FFT length 53248 = 52 K:
(A - B) mod C has Res64,35m1,36m1: 0x32E74AF916FA4C92,25999072071,15353862932.
GCD(A[1063296 bits], B[1063269 bits]) = 1
Time for GCD = 00:00:00.113
Time for GCD = 00:00:00.113
Cofactor is not a prime power.
If using the manual results submission form at mersenne.org, paste the following JSON-formatted results line:
{"status":"C", "exponent":1063427, "known-factors":["68506830638546017","9191962833192559119894251405401"], "worktype":"PRP-3", "res64":"34F046857B8DEDB7", "residue-type":5, "fft-length":53248, "shift-count":0, "error-code":"00000000", "program":{"name":"Mlucas", "version":"20.1.1"}, "timestamp":"2024-02-28 23:22:08 UTC"}
The problem appears to be that Mlucas is unable to restart from a saved residue (which is required for the Fermat numbers as there are two worktodo formats for the two tests, the primality test using Fermat,Test=, and the cofactor test using PRP=).
Note. The following test was devised by Robert Gerbicz in conversation with Ernst Mayer here.
The cofactor test tries a “sanity check” on each known factor prior to running the test, which has the effect of testing whether the residue R has been correctly calculated at any point of the computation:
Computing 1060000-squaring residue R (mod known prime q = 68506830638546017)
A: R == 13206716689333421 (mod q)
B: R == 13206716689333421 (mod q)
Computing 1060000-squaring residue R (mod known prime q = 9191962833192559119894251405401)
A: R == 3548111304294208065146791942045 (mod q)
B: R == 3548111304294208065146791942045 (mod q)
Had the A and B values been found unequal, then the full residue R would be incorrect.
A is derived directly from the full residue, so A ≡ 3½(Fm–1) (mod Fm mod q); and
B is calculated solely from the prime factor q: B ≡ 322^m–1 (mod q–1) (mod q); if q is a prime factor dividing Fm such that 3q–1 ≡ 1 (mod q) then these quantities should always be in agreement, modulo q. (These are the Fermat number equations and the Mersenne case is similar.)
If the residue is saved correctly and is saved at the right iteration, Mlucas restarts and the cofactor test proceeds correctly. The Mersenne cofactor test can be run separately if a residue is saved and a new factor is found later; for the Fermat test, the saved residue must be from a Pépin test (2m–1 modular squaring iterations) or the value is rejected and the test refuses to run. For this reason, Fermat testing must consist of two separate worktodo entries, e.g.:
Again seemingly a problem for the Fermats; Mlucas 21 now has cofactor testing, where either a Mersenne or Fermat number with known factors is PRP tested for compositeness of the cofactor. This is achieved by doing a 3-PRP test of the large number, then exponentiating 3 by the product of known factors – 1, and subtracting the two results modulo the cofactor:
P = Q · C, where P = the Mersenne or Fermat number; Q = p1·p2·…·pi is product of known factors, and C is the cofactor; A = 3P–1 (mod P); B = 3Q–1 (mod P); and by Fermat’s little theorem, A – B (mod C) should be non-zero if C is composite; otherwise C is probably prime to the base 3Q.
The issue with the Fermat numbers is that the A result is difficult to obtain (Ernst spent 5 years chasing the result for F30) so the
worktodolineshould save the final residue of the Pépin test, which is 3½(F30–1) (mod F30), which is exactly one modular squaring before obtaining the A value.
This does not seem to be happening with the Pépin test. Instead when the PRP test completes the Res64 modulo 264 residue is written to stdout and the .stat file, but the full residue is not saved, preventing the cofactor test.
Edited to add: there is a rather hacky workaround to generate the final residue, but it would be preferable not to have to resort to using anything so crude; and indeed there are other superior methods.
The same seems to be true of Mersenne numbers, however the cofactor code fortunately runs correctly and immediately after the primality test as there is only one
worktodoentry, and so it does not need to “restart”; e.g. having added aworktodoentry ofI obtained the following result which matches previously tested results with mprime:
The problem appears to be that Mlucas is unable to restart from a saved residue (which is required for the Fermat numbers as there are two
worktodoformats for the two tests, the primality test usingFermat,Test=, and the cofactor test usingPRP=).Note. The following test was devised by Robert Gerbicz in conversation with Ernst Mayer here.
The cofactor test tries a “sanity check” on each known factor prior to running the test, which has the effect of testing whether the residue R has been correctly calculated at any point of the computation:
Had the A and B values been found unequal, then the full residue R would be incorrect.
A is derived directly from the full residue, so A ≡ 3½(Fm–1) (mod Fm mod q); and
B is calculated solely from the prime factor q: B ≡ 322^m–1 (mod q–1) (mod q); if q is a prime factor dividing Fm such that 3q–1 ≡ 1 (mod q) then these quantities should always be in agreement, modulo q. (These are the Fermat number equations and the Mersenne case is similar.)
If the residue is saved correctly and is saved at the right iteration, Mlucas restarts and the cofactor test proceeds correctly. The Mersenne cofactor test can be run separately if a residue is saved and a new factor is found later; for the Fermat test, the saved residue must be from a Pépin test (2m–1 modular squaring iterations) or the value is rejected and the test refuses to run. For this reason, Fermat testing must consist of two separate
worktodoentries, e.g.: