Gerbicz error checking

Gerbicz error checking is a technique to verify validity of primality tests. It was proposed by Robert Gerbicz at MersenneForum in August 2017.

Among GIMPS clients, the technique is used to ensure validity of PRP tests for Mersenne numbers:

• in Prime95 since version 29.4
• in gpuOwL.

It is also used by LLR and LLR2 to ensure validity of Proth tests and PRP tests on base-2 Riesel prime candidates, and by those programs and PRST in an extended version for PRP tests on additional number forms.

Theory

The following describes the original formulation of the Gerbicz error check for Proth tests, as described in this MersenneForum thread:

1. Let [math]\displaystyle{ p }[/math] be a Proth number, and let [math]\displaystyle{ k }[/math], [math]\displaystyle{ n }[/math], and [math]\displaystyle{ a }[/math] be defined as on Proth's theorem.
2. Let [math]\displaystyle{ L }[/math] be a constant (originally defined as 2000, but described as possibly depending on [math]\displaystyle{ n }[/math]).
3. We have the following equations:
   1. [math]\displaystyle{ u(t) \equiv (a^k)^{2^t} \pmod{p} }[/math]
   2. [math]\displaystyle{ d(t) \equiv \displaystyle\prod_{i=0}^t u(iL) \pmod{p} }[/math]
   3. [math]\displaystyle{ d(t+1) \equiv d(t)*u((t+1)L) \pmod{p} }[/math]
   4. [math]\displaystyle{ d(t+1) \equiv u(0)*d(t)^{2^L} \pmod{p} }[/math]
4. Continue...

See also

• Jacobi error checking

External links

• Original proposal of the technique for Proth numbers
• Original proposal of the technique for Mersenne numbers