View Single Post
Old 2021-09-24, 14:29   #66
kriesel's Avatar
Mar 2017
US midwest

171816 Posts

Originally Posted by Happy5214 View Post
Gerbicz should catch more errors than Jacobi (key word is catch; the actual number of bad iterations should be roughly equal either way), but also have the ability to correct the bad iterations more efficiently (wrt granularity/frequency of checks and the probability of an error being caught), thus producing more reliable results.
Correct. Jacobi symbol check is done infrequently, only ~twice a day because it is computationally costly. Its detection rate is only ~50% of errors. If done after every LL iteration it would cost more than it might save, and still only detect ~75% of errors. For Mersennes it yields +1 or -1 IIRC; there are only 3 possible values in general, 1, -1, 0, so an error going undetected is quite probable. This post describing the Jacobi symbol check led to some quick implementation, and consideration of what other checks might be available.
Robert Gerbicz' post describing the check for PRP followed days later. Both Jacobi and GEC are typically applied by the software authors to use around 0.2% of computing time by default, with some user control for more or less cost & frequency.

Gerbicz' check is highly effective, since it can return one of a great many values, and only one will match.
Empirically, PRP/GEC has shown ~24ppm error in completed tests, ~800 times lower than LL. And some of that error count was from outside / after the GEC check, handling the final residue produced. Prime95 got hardened against that after some such errors were identified. See
These number-theory based checks are in addition to and independent of other inexpensive measures, such as round-off magnitude checking, or sum of inputs vs. sum of outputs.
kriesel is offline   Reply With Quote