Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Jacobi error checking

From Prime-Wiki
Jump to: navigation, search

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

External links