An Efficient Modular Exponentiation Proof Scheme

MaRDI QIDQ6412519zbMATH OpenFDO

Authors Darren Li, Yves Gallot

Publication date 16 September 2022

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to number theory (11-04)

Abstract: 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^{n}equivrpmodm$ 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.

This page was built for publication: An Efficient Modular Exponentiation Proof Scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6412519)