Jacobi error checking

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).

See also

• Gerbicz error checking

External links

• Original explanation of the method