An Efficient Modular Exponentiation Proof Scheme. (arXiv:2209.15623v2 [cs.CR] UPDATED)

We present an efficient proof scheme for any instance of left-to-right
modular exponentiation, used in many computational tests for primality.
Specifically, we show that for any $(a,n,r,m)$ the correctness of a computation
$a^nequiv rpmod m$ can be proven and verified with an overhead negligible
compared to the computational cost of the exponentiation. Our work generalizes
the Gerbicz-Pietrzak proof scheme used when $n$ is a power of $2$, and has been
successfully implemented at PrimeGrid, doubling the efficiency of distributed
searches for primes.