| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
Navigation
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Jacobi error checking"
(restored) |
(Adding to new category) |
||
| Line 15: | Line 15: | ||
==External links== | ==External links== | ||
*[http://www.mersenneforum.org/showthread.php?p=465082#post465082 Original explanation of the method] | *[http://www.mersenneforum.org/showthread.php?p=465082#post465082 Original explanation of the method] | ||
| − | [[Category: | + | |
| + | [[Category:Error checking]] | ||
Latest revision as of 18:36, 27 September 2023
Jacobi error checking is a probabilistic technique to verify validity of Lucas-Lehmer test computation.
It is used in Prime95 software since version 29.3. The feature was proposed by user error at MersenneForum in August 2017. [1]
The method
The method is based on the fact that for any valid residue in the LL test:
- Jacobi symbol of the residue plus 2 [math]\displaystyle{ \left(\frac{Res+2}{M_p}\right) }[/math] has to be +1
- Jacobi symbol of the residue minus 2 [math]\displaystyle{ \left(\frac{Res-2}{M_p}\right) }[/math] has to be -1
When both of these values are positive, the corresponding values for subsequent residues will be also positive allowing to spot an error even if the check is run not on every iteration (which would be too slow while still not completely ensuring validity of the result).
