On the Gerbicz error check
This is a shorter than average post discussing the Gerbicz error check.
Theorem (Proth 1878): For $k$ odd and $n$ integer, $k2^n+1$ is prime if, and only if, for some quadratic nonresidue $a$, we have $a^{\frac{p-1}{2}}\equiv -1\pmod p$.
This gives an efficient primality test for Proth numbers, where the bottleneck is efficiently computing $(a^k)^{2^{n-1}}$ modulo $p$. During such a computation we need to square a value $n-1$ times, using fast multiplication i.e. FFT-based multiplication algorithms. However, especially for GPU and related implementations of FFT, such algorithms are prone to precision errors and one error renders the following multiplications all incorrect.
In order to prevent the risk of restarting the entire computation, we need to check our computation as we do it. It turns out, as Robert Gerbicz has shown, that this is efficiently completable.
Here’s a high-level overview of this error check by Pavel Atnashev, adequately titled “How Magic Works”:
Consider the sequence we are calculating $\{u_i=(a^k)^{2^i}\}_{i=0}^{n-1}$. Then for $i>0$, $u_i=u_{i-1}^2$. Define a checkpointing constant $L=1000$; now define a series of checkpoints as a prefix product of every L-th element, i.e.
$$r_i\equiv\prod_{j=0}^i u_{jL}\pmod p$$
Then we must have $r_i\equiv r_{i-1}\cdot (a^k)^{2^{iL}}\pmod p$, by definition. On the other hand,
$$r_i\equiv\prod_{j=0}^i (a^k)^{2^{jL}}\equiv (a^k)\prod_{j=1}^i (a^k)^{2^{jL}}\equiv (a^k)\left(\prod_{j=0}^{i-1} (a^k)^{2^{jL}}\right)^{2^L}\equiv (a^k)r_{i-1}^{2^L}\pmod p$$
This process effectively “compresses” the first $i-1$ checkpoints and advances them together $L$ steps. In other words, if any of $r_i$ isn’t really $r_{i-1}\cdot (a^k)^{2^{iL}}$, then the equivalence won’t hold! Thus we can check if $r_i\equiv (a^k)r_{i-1}^{2^L}\pmod p$ every $L$ checkpoints; if we find an error, we will only have to roll back $L^2$ steps, which is only a fraction of the $n\approx 4\times 10^7$ leading edge.
In fact, we can generalze this error check procedure to adverserial proof-of-computation checking.
Suppose Alice wishes for Bob to prove that he has indeed computed $(a^k)^{2^{n-1}}$, instead of, say, faking a random result, but Alice doesn’t have time to completely replicate Bob’s work. Then Alice can ask Bob to send $u_{0},u_{L},u_{2L},\dots$; then, Alice verifies that
$$\prod_{i=1}^ku_{iL}\equiv \left(\prod_{i=0}^{k-1}u_{iL}\right)^{2^L}\pmod p$$
If there exists any $i$ where $u_{iL+L}\not\equiv u_{iL}^{2^L}\pmod p$, the entire equivalence fails.
But wait! What if Bob specifically constructs $u_{iL}$ to satisfy this equivalence? In that case we can randomly “salt” each computation. Specifically let us randomly generate small $x_i$ for each $i=0,1,\dots,k-1$; then, the equivalence we seek is
$$\prod_{i=1}^ku_{iL}^{x_{i-1}}\equiv \left(\prod_{i=0}^{k-1}u_{iL}^{x_i}\right)^{2^L}\pmod p$$
This is enough, as now there is no way for Bob to predict ahead of time the equivalence he needs to satisfy.
UPDATE 4/25
I got the Gerbicz error check to work in the general case :DDD here’s its application to Genefer
The Genefer PRP test efficiently checks $x^N \overset{\text{?}}{\equiv} 1\pmod{N+1}$ for $N=b^k$ where $b$ is even and $k$ is a power of two to implement the Fermat probable prime test for Generalized Fermat numbers. This is a rough sketch of a practical double check scheme for this test.
Genefer evaluates $x^N$ using left-to-right binary exponentiation, calculating
$$x^{N}\leftarrow x^{\lfloor\frac{N}{2}\rfloor}\leftarrow x^{\lfloor\frac{N}{4}\rfloor}\leftarrow\dots\leftarrow x^{\lfloor\frac{N}{2^l}\rfloor}\leftarrow\dots$$
with each arrow representing a squaring and a multiplication by $x$ if necessary.
If we checkpoint every $B$ steps and at the final step, then our checkpoints can be expressed as $x$ to the power of ${\lfloor\frac{N}{2^{Bl}}\rfloor}$ for integer $l$. The step between checkpoints can then be expressed as
$$\begin{align*}x^{\left\lfloor\frac{N}{2^{Bl}}\right\rfloor}\overset{\text{?}}{\equiv} x^{\left\lfloor\frac{N}{2^{Bl+B}}\right\rfloor2^B}x^{\left\lfloor\frac{N}{2^{Bl}}\right\rfloor\bmod 2^B}\pmod{N+1}\end{align*}$$
A double check can then be expressed as
$$\begin{align*}\prod_lx^{\left\lfloor\frac{N}{2^{Bl}}\right\rfloor}&\overset{\text{?}}{\equiv} \prod_lx^{\left\lfloor\frac{N}{2^{Bl+B}}\right\rfloor2^B}x^{\left\lfloor\frac{N}{2^{Bl}}\right\rfloor\bmod 2^B}\pmod{N+1}\\\prod_lx^{\left\lfloor\frac{N}{2^{Bl}}\right\rfloor}&\overset{\text{?}}{\equiv} \left(\prod_lx^{\left\lfloor\frac{N}{2^{Bl+B}}\right\rfloor}\right)^{2^B}x^{\sum_l\left(\left\lfloor\frac{N}{2^{Bl}}\right\rfloor\bmod 2^B\right)}\pmod{N+1}\end{align*}$$
The LLR2 salting and compression methods are all applicable; the only difference between this and the Proth double check scheme is the extra $x^{\sum_l\left(\left\lfloor\frac{N}{2^{Bl}}\right\rfloor\bmod 2^B\right)}$ term.