Mluces incorrectly states that M37 is no prime

[Hermann-SW]

I followed Linux build instructions, ugraded to latest and all dev prerequistites were installed already. I did run ./Mlucas -s large in obj directory. Then I did run Mlucase on M37. I run "Ubuntu 22.04.4 LTS" on "AMD Ryzen 9 7950X 16-Core Processor". @kriesel mentioned in this posting that I should report, and that you might be interested in p3021377.stat, so I attach that file here (gziping was needed to be able to attach here): p3021377.stat.gz

This is complete execution stating M3021377 is not prime, but I see some warnings as well. I will keep all files in obj directory in case you want other files as well.

hermann@7950x:~/Mlucas/obj$ taskset -c 0-7,16-23 ./Mlucas 

    Mlucas 20.1.1

    http://www.mersenneforum.org/mayer/README.html

INFO: testing qfloat routines...
System total RAM = 31190, free RAM = 28673
INFO: 28673 MB of free system RAM detected.
CPU Family = x86_64, OS = Linux, 64-bit Version, compiled with Gnu C [or other compatible], Version 11.4.0.
INFO: Build uses AVX512 instruction set.
INFO: Using prefetch.
INFO: Using inline-macro form of MUL_LOHI64.
INFO: Using FMADD-based 100-bit modmul routines for factoring.
INFO: MLUCAS_PATH is set to ""
INFO: using 64-bit-significand form of floating-double rounding constant for scalar-mode DNINT emulation.
INFO: testing IMUL routines...
INFO: Testing 64-bit 2^p (mod q) functions with 100000 random (p, q odd) pairs...
INFO: System has 32 available processor cores.
INFO: testing FFT radix tables...
User did not set LowMem in mlucas.ini ... allowing all test types.
User did not set CheckInterval in mlucas.ini ... using default.
No CPU set or threadcount specified ... running single-threaded.
Set affinity for the following 1 cores: 0.
Setting ITERS_BETWEEN_CHECKPOINTS = 10000.
 looking for worktodo.txt file...
 worktodo.txt file found...reading next assignment...
 worktodo.txt entry: PRP=1,2,3021377,-1,75,0

INFO: FFT length 163840 = 160 K not found in the 'mlucas.cfg' file.

 Return with code ERR_RUN_SELFTEST_FORLENGTH

           Mlucas selftest running.....

/****************************************************************************/

User did not set LowMem in mlucas.ini ... allowing all test types.
User did not set CheckInterval in mlucas.ini ... using default.
NTHREADS = 1
Setting ITERS_BETWEEN_CHECKPOINTS = 10000.
 worktodo.txt file not found...using user-supplied command-line exponent p = 3253153
INFO: Maximum recommended exponent for FFT length (160 Kdbl) = 3269550; p[ = 3253153]/pmax_rec = 0.9949849368.
Initial DWT-multipliers chain length = [hiacc] in carry step.
M3253153: using FFT length 160K = 163840 8-byte floats, initial residue shift count = 771231
This gives an average   19.855670166015624 bits per digit
Using complex FFT radices       160        16        32
mers_mod_square: Init threadpool of 1 threads
Using 1 threads in carry step
100 iterations of M3253153 with FFT length 163840 = 160 K, final residue shift count = 2304690
Res64: 9AFD3618C164D1B4. AvgMaxErr = 0.251803153. MaxErr = 0.312500000. Program: E20.1.1
Res mod 2^35 - 1 =          16551334620
Res mod 2^36 - 1 =          55616214582
Clocks = 00:00:00.077

User did not set LowMem in mlucas.ini ... allowing all test types.
User did not set CheckInterval in mlucas.ini ... using default.
NTHREADS = 1
Setting ITERS_BETWEEN_CHECKPOINTS = 10000.
 worktodo.txt file not found...using user-supplied command-line exponent p = 3253153
INFO: Maximum recommended exponent for FFT length (160 Kdbl) = 3269550; p[ = 3253153]/pmax_rec = 0.9949849368.
Initial DWT-multipliers chain length = [hiacc] in carry step.
M3253153: using FFT length 160K = 163840 8-byte floats, initial residue shift count = 2304690
This gives an average   19.855670166015624 bits per digit
Using complex FFT radices       160        32        16
mers_mod_square: Init threadpool of 1 threads
100 iterations of M3253153 with FFT length 163840 = 160 K, final residue shift count = 1537965
Res64: 9AFD3618C164D1B4. AvgMaxErr = 0.242770822. MaxErr = 0.312500000. Program: E20.1.1
Res mod 2^35 - 1 =          16551334620
Res mod 2^36 - 1 =          55616214582
Clocks = 00:00:00.076

User did not set LowMem in mlucas.ini ... allowing all test types.
User did not set CheckInterval in mlucas.ini ... using default.
NTHREADS = 1
Setting ITERS_BETWEEN_CHECKPOINTS = 10000.
 worktodo.txt file not found...using user-supplied command-line exponent p = 3253153
INFO: Maximum recommended exponent for FFT length (160 Kdbl) = 3269550; p[ = 3253153]/pmax_rec = 0.9949849368.
Initial DWT-multipliers chain length = [hiacc] in carry step.
M3253153: using FFT length 160K = 163840 8-byte floats, initial residue shift count = 1537965
This gives an average   19.855670166015624 bits per digit
Using complex FFT radices        40         8        16        16
mers_mod_square: Init threadpool of 1 threads
Using 1 threads in carry step
100 iterations of M3253153 with FFT length 163840 = 160 K, final residue shift count = 1468725
Res64: 9AFD3618C164D1B4. AvgMaxErr = 0.320982143. MaxErr = 0.375000000. Program: E20.1.1
Res mod 2^35 - 1 =          16551334620
Res mod 2^36 - 1 =          55616214582
Clocks = 00:00:00.091

User did not set LowMem in mlucas.ini ... allowing all test types.
User did not set CheckInterval in mlucas.ini ... using default.
NTHREADS = 1
Setting ITERS_BETWEEN_CHECKPOINTS = 10000.
 worktodo.txt file not found...using user-supplied command-line exponent p = 3253153
INFO: Maximum recommended exponent for FFT length (160 Kdbl) = 3269550; p[ = 3253153]/pmax_rec = 0.9949849368.
Initial DWT-multipliers chain length = [hiacc] in carry step.
M3253153: using FFT length 160K = 163840 8-byte floats, initial residue shift count = 1468725
This gives an average   19.855670166015624 bits per digit
Using complex FFT radices        20        16        16        16
mers_mod_square: Init threadpool of 1 threads
WARN: At line 273 of file ../src/radix20_ditN_cy_dif1.c:
radix20_ditN_cy_dif1: No AVX-512 support; Skipping this leading radix.

 Return with code ERR_RADIX0_UNAVAILABLE
Error detected - this radix set will not be used.
INFO: 3 of 4 radix-sets at FFT length 160 K passed - writing cfg-file entry.
User did not set LowMem in mlucas.ini ... allowing all test types.
User did not set CheckInterval in mlucas.ini ... using default.
NTHREADS = 1
Setting ITERS_BETWEEN_CHECKPOINTS = 10000.
 looking for worktodo.txt file...
 worktodo.txt file found...reading next assignment...
 worktodo.txt entry: PRP=1,2,3021377,-1,75,0

INFO: Maximum recommended exponent for FFT length (160 Kdbl) = 3269550; p[ = 3021377]/pmax_rec = 0.9240956707.
Initial DWT-multipliers chain length = [long] in carry step.
INFO: primary restart file p3021377 not found...looking for secondary...
INFO: no restart file found...starting run from scratch.
mers_mod_square: Init threadpool of 1 threads
At iter ITERS_BETWEEN_GCHECK_UPDATES = 1000: RES_SHIFT = 284483
Recovered initial shift 284483
M3021377 is not prime. Program: E20.1.1. Final residue shift count = 1703676.
If using the manual results submission form at mersenne.org, paste the following JSON-formatted results line:
{"status":"C", "exponent":3021377, "worktype":"PRP-3", "res64":"0000000000000001", "residue-type":1, "fft-length":163840, "shift-count":1703676, "error-code":"00000000", "program":{"name":"Mlucas", "version":"20.1.1"}, "timestamp":"2024-03-28 19:17:32 UTC"}

 INFO: restart file p3021377 found...reading...
Unable to delete secondary restart file q3021377
hermann@7950x:~/Mlucas/obj$ 

[Hermann-SW]

This was the content of worktodo.txt on starting execution, got that from @kriesel:

PRP=1,2,3021377,-1,75,0

These are the latest files in obj directory after build:

hermann@7950x:~/Mlucas/obj$ ls -lst | head -12
total 35404
   68 -rw-rw-r-- 1 hermann hermann    64820 Mar 28 20:17 p3021377.stat
    4 -rw-rw-r-- 1 hermann hermann      259 Mar 28 20:17 results.txt
    0 -rw-rw-r-- 1 hermann hermann        0 Mar 28 20:17 worktodo.txt
  740 -rw-rw-r-- 1 hermann hermann   755423 Mar 28 20:17 p3021377
  740 -rw-rw-r-- 1 hermann hermann   755423 Mar 28 20:17 p3021377.G
    4 -rw-rw-r-- 1 hermann hermann     2347 Mar 28 19:38 mlucas.cfg
    4 -rw-rw-r-- 1 hermann hermann      104 Mar 28 18:00 p173431.stat
    4 -rw-rw-r-- 1 hermann hermann      104 Mar 28 18:00 p44657.stat
    4 -rw-rw-r-- 1 hermann hermann      104 Mar 28 18:00 p22679.stat
 2228 -rw-rw-r-- 1 hermann hermann  2280958 Mar 28 17:52 build.log
12824 -rwxrwxr-x 1 hermann hermann 13129280 Mar 28 17:52 Mlucas
hermann@7950x:~/Mlucas/obj$ 

[tdulcet]

Thanks for the bug report and the detailed information! This is actually very concerning, as the final residue of 1 in the JSON result in your provided .stat file means the exponent was prime as expected, so the PRP test ran correctly, but for some reason Mlucas is not detecting that. I am currently running this on my system to see if I can reproduce the issue.

I did run ./Mlucas -s large in obj directory.

This is a very small exponent, so you would need to run the tiny self-test, which should resolve those errors/warning. Just delete the mlucas.cfg file and then run: ./Mlucas -s tiny. If you want to run most of the self-tests (teensy, tiny, small, medium and large) at once, run: ./Mlucas -s all instead. As you may know, you would need to add the -cpu or -core options to each Mlucas command if you want use more than one CPU thread on your system, .

From reading your conversation on the forum, if you want to prove the primality of this exponent, you would actually need to perform an LL test instead of a PRP test, in both MPrime and Mlucas. You may want to try that to see if it correctly identifies this exponent as prime:

Test=3021377,75,1

(Note that the Kriesel you mentioned here on GitHub is probably not the same Ken Kriesel from the forum.)

[tdulcet]

I was able to reproduce the issue. It occurs with both Mlucas v20.1.1 and v21:

[2024-03-29 03:34:46] M3021377 Iter# = 3021377 [100.00% complete] clocks = 00:00:01.809 [  1.3137 msec/iter] Res64: 0000000000000009. AvgMaxErr = 0.058192349. MaxErr = 0.085937500. Residue shift count = 1587598.
M3021377 is not prime. Program: E20.1.1. Final residue shift count = 1587598.
If using the manual results submission form at mersenne.org, paste the following JSON-formatted results line:
{"status":"C", "exponent":3021377, "worktype":"PRP-3", "res64":"0000000000000001", "residue-type":1, "fft-length":163840, "shift-count":1587598, "error-code":"00000000", "program":{"name":"Mlucas", "version":"20.1.1"}, "timestamp":"2024-03-29 10:34:46 UTC"}

The bug seems to be related to this index in the residue array, which is nonzero:

i=86089, j=86425: a[j]=9216

Maybe an off by one error? Here here is the code that checks for primality: https://github.com/primesearch/Mlucas/blob/13860639c58632248195e33c29c13117c93061f9/src/Mlucas.c#L2437-L2443 @ldesnogu - Any insights?

[ldesnogu]

I'm afraid this code doesn't help in any way: it just proves the computation was wrong and the expected result (which this code is supposed to check) is not what it should be. The error could have happened in previous steps. A way to check that could be to write a simpler version of the test (with gmp?) and test at each step the intermediate results match. I'm not sure if this is feasible.

[tdulcet]

OK, thanks for the information. GEC runs successfully near the end of the PRP test (after 3 million iterations), so presumably the last residue is correct (the res64 does show the expected value of 9 for a prime). Therefore, the bug must be with the modular division by 9 at the end, which is the previous step. The final res64 in the JSON result does have the expected value of 1, but the rest of the residue is not all zeros as expected, which is shown by the result of that above for loop. The question is does this mean all PRP tests performed by Mlucas were bad.

[xanthe-cat]

I have some additional news that is probably not welcome, based on having now trialled this bug on 15 intermediate Mersenne primes (the 24th to 38th, with exponents from 19937 to 6972593) using 3-PRP tests, 8 MPs (19937 to 216091) using 5-PRP tests, and 12 MPs (19937 to 1398269) using 7-PRP tests. To use a base other than 3 requires commenting out an assertion at line 698, but once that has been done any base > 1 and not a power of 2 is permitted. Base 5-PRP testing of a Mersenne prime yields a final residue of 5² so the modular division by 25 yields 0x1 as expected. However for base 7 and the final residue of 7², the modular division by 49 yields a wrong value of 0x0. This is a show-stopper and I can imagine why Ernst had disabled bases other than 3 for PRP testing.

[xanthe-cat]

Pull request #17 (just added) should address the problem with 3–PRP and 5–PRP tests. The 7–PRP modular division bug is a separate problem that is unresolved.

[xanthe-cat]

“The 7–PRP modular division bug is a separate problem that is unresolved.” This has been raised as issue #18 which is to be fixed with pull #23.

[Kriesel]

(Note that the Kriesel you mentioned here on GitHub is probably not the same Ken Kriesel from the forum.)

True story haha

[Hermann-SW]

(Note that the Kriesel you mentioned here on GitHub is probably not the same Ken Kriesel from the forum.)

True story haha

I should have known ! I am HermannSW on Raspberry forum, twitter, ... and had to choose Hermann-SW on github because somebody else used HermannSW on github already when I joined …