| 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 |
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:
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:
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, with [math]\displaystyle{ a }[/math] a quadratic non-residue modulo [math]\displaystyle{ p }[/math]. Let [math]\displaystyle{ L }[/math] be a constant (originally defined as 2000, but described as possibly depending on [math]\displaystyle{ n }[/math]). We have the following equations:
- [math]\displaystyle{ u(t) \equiv (a^k)^{2^t} \pmod{p} }[/math]
- [math]\displaystyle{ d(t) \equiv \displaystyle\prod_{i=0}^t u(iL) \pmod{p} }[/math]
- [math]\displaystyle{ d(t+1) \equiv d(t)*u((t+1)L) \pmod{p} }[/math]
- [math]\displaystyle{ d(t+1) \equiv u(0)*d(t)^{2^L} \pmod{p} }[/math]
Then [math]\displaystyle{ p }[/math] is prime if and only if [math]\displaystyle{ u(p-1) \equiv -1 \pmod{p} }[/math]. We store only the last term of the [math]\displaystyle{ d }[/math] sequence to use identity (3), and store [math]\displaystyle{ u(0) = a^k \pmod{p} }[/math], as well as the most recent [math]\displaystyle{ d(z) }[/math] and [math]\displaystyle{ u(z) }[/math], where [math]\displaystyle{ z \mid L^2 }[/math].
Every [math]\displaystyle{ L }[/math] terms of the [math]\displaystyle{ d }[/math] sequence we check the identity of (4). If this does not hold, then we roll back. If we roll back too much (e.g. 100 times to the same term), then we just restart the computation completely.
At the last few squarings in [math]\displaystyle{ u }[/math], we also force an error checking computation of (4) (in that [math]\displaystyle{ i }[/math] when [math]\displaystyle{ i \mid L }[/math] and [math]\displaystyle{ i + L \geq n }[/math], this means only one extra checking of (4).) This leaves all potential errors in the (at most) last [math]\displaystyle{ L }[/math] squarings in [math]\displaystyle{ u }[/math], or very unlikely errors earlier in [math]\displaystyle{ u }[/math] or [math]\displaystyle{ d }[/math].
The overhead is [math]\displaystyle{ n/L }[/math] mulmods in (3) and [math]\displaystyle{ n / L^2 * L = n/L }[/math] squaremod in (4) and [math]\displaystyle{ n / L^2 }[/math] mulmods in (4), so over the [math]\displaystyle{ n-1 }[/math] mulmods of the Proth test, there are approximately [math]\displaystyle{ n/1000 }[/math] mulmods, if we count everything in mulmods. Therefore, the overhead is 0.1% in time.
We could check all terms of [math]\displaystyle{ d }[/math], but in that case the overhead in the error checking would be [math]\displaystyle{ n / L * (L+1) \gt n }[/math] mulmods, and that is a lot, slightly more time what we spend on the Proth test squarings.
