View Single Post
Old 2022-02-10, 18:04   #9
kriesel's Avatar
Mar 2017
US midwest

11101011110012 Posts
Default Why no one should run LL if they can run PRP with proof generation instead

Run time, reliability, efficiency.

All new first primality tests should be PRP type, with proof generation whenever possible. PRP/GEC/proof/Cert is much more reliable, and effectively twice as fast, since it essentially eliminates the typical 2% LL error rate leading to occasional triple checks or further, and reduces verification to typically under 1% of what an LL DC requires (>99% reduction!). If the choices are between Gpuowl PRP or CUDALucas LL, the savings are even more dramatic, nearly 4:1 in some scenarios. PRP with proof generation also provides much faster indication of system reliability (typically hours), than does LL. (Typically years, 8.2 in that example, for an LL DC to occur; examples over 9 years also exist, including:
Ten years:

Since the reliability advantage of PRP/GEC over LL also applies to double checking, most LL first tests will never have LLDC run. They will instead be verified composite more reliably and more quickly by a first time PRP/GEC/proof and cert. So in the usual >999,999 ppm case of a composite Mersenne number, an LL first primality test is a complete waste of time and computing resources. (An LL DC on an LL first test is also a small percentage waste of time, and is much less reliable than PRP/GEC. As is LL TC, LL QC, etc compared to PRP/GEC/proof/cert for reasonably close to optimal proof powers.)

Mprime/prime95 (~v30.3 or higher), and GpuOwl (~v6.11-316 and later) are available in proof-capable forms. Mlucas proof file generation capability was planned for V20.x, but I think that slipped past v20.1 to V21 because P-1 implementation in V20 took a lot of effort, followed by some bug finding and fixing fun, with current latest available Mlucas at V20.1.1 2022-07-06. (Lucas-Lehmer tests will still be used if/when PRP returns a probable prime indication for a suspected new Mersenne prime discovery, to confirm by multiple independent tests by separate hardware, software, and participants. The person reporting a PRP probable prime indication from a first test would still be regarded as the discoverer.)
In occasional sampling ~2021-01-24 of over 130 primality testing assignments in 101-102M, 38% were LL, 62% PRP. That LL frequency was much too high.
As of 2021-01-27 1540 UTC in 101-102M primality testing of 273 active assignments, 57 LL, 21%, better. For 101M-103M as of 2021-03-28 ~2010 UTC, 23 LL of 132, 17%. On 2021-04-21 ~1500 UTC, for 102M-104M, first 1000 contained only 41 LL, 4.1% On 2021-04-30 ~1800 UTC, for 102M-104M, first 1000 contained only 11 LL, 1.1%. Let's keep moving away from inefficient LL first tests, that are very slowly double-checked, toward complete conversion to the far more reliable and efficient PRP/GEC/proof/Cert that also provides very rapid verification. A check of "recently cleared" 2021-07-19 showed a mix of primality tests for exponents >100M, 12 LL (mostly elapsed time over a year) vs. 924 PRP, ~1.3%. Drive LL percentage toward 0%, PRP with proof generation toward 100%. As of 2021-08-28, shows only PRP in 1000 queued tests. It's unclear how many will produce a proof file.
GPUs that can run either CUDALucas or Gpuowl should run PRP/GEC/proof on Gpuowl as primality tests, not LL, and not CUDALucas. (That would include all Google Colab GPU models. The Google Drive free space is sufficient.)

Exceptional cases
If attempting primality testing above 1G exponent, there is currently nowhere to submit proof files or primality test results, and no software to certify them above 1.17G. Proof files should be preserved where they are generated and held until that changes. PRP DC with GEC is likely to work. LL is likely to take dozens of attempts, or paired attempts with frequent interim residue comparison manually, to obtain matching final residues.

If running on very low storage space hardware, run low proof power PRP with proof. (Mprime/prime95, and numerous versions of gpuowl can do that. Eventually Mlucas will also have proof generation capability.)

If running on GPUs or CPUs so old that PRP is not available for them, consider replacing with newer more energy efficient hardware.

If part of the select small team confirming a PRP-P result is in fact a new Mersenne prime discovery, then LL is necessary to prove primality. Such runs should be performed on the fastest available highly reliable hardware, in differing software, by multiple individuals. For large exponents it is likely comparison of interim residues will be useful in indicating reliable progress or detecting computation errors along the way. Hardware with ECC ram is recommended.

On extremely reliable hardware (no GEC errors detected in dozens of successive runs; probably ECC system ram), it might be slightly more efficient to run LLDC than PRP/GEC/proof-gen, IF the first LL test was also performed on a highly reliable combination of hardware and software. Generally the reliability of another user's system will not be known to the user performing such a DC.

Empirical data
Following is a summary of approximately 2000 each of my own runs. LL error rate is an increasing function of exponent (more likely run time), and extrapolates to greater than 60% error rate at near 1G exponent. These were run on essentially the same hardware pool. Error rate on PRP guarded by the excellent GEC is zero.
kriesel LL track record

exponent range  verified ll  unverified  later factored  bad results  %bad/(bad+verified)
p<59M 		935		0		12		12	1.28
59M-100M	864		453		4		23	2.66
100M-200M	103		4		0		8	7.77
200M-350M	12		3		0		2	14.29 
350M-500M	0		1		0		0	na
500M+		0		0		0		0	na
totals		1914		461		16		45	average 2.35%

etc on 2023-02-24 (without specifying dates)
kriesel PRP track record

exponent range	verified prp	unverified	factored	bad	%bad/verified
p<75M		837		2		4		0	0
75M-100M	654		303	        1		0	0
100M-150M	351		9		2		0	0
150M-300M	172		9		0		0	0
300M-500M	61		7		1		0	0
500M-1G		20		11		0		0	0
totals		2095		341		8		0	0

etc on 2023-02-24 (without specifying dates)
See also and

Top of reference tree:
Attached Files
File Type: pdf ll track record.pdf (16.7 KB, 3 views)

Last fiddled with by kriesel on 2023-03-26 at 17:36 Reason: minor edit
kriesel is online now