论文标题
有效的模块化启动证明方案
An Efficient Modular Exponentiation Proof Scheme
论文作者
论文摘要
我们为任何左右模块化凸起的任何实例提供了有效的证明方案，该方案用于许多计算测试用于原始性。具体而言，我们表明，对于任何$（a，n，r，m）$，与指示的计算成本相比，可以证明并用高架可忽略的计算$ a^n \ equiv r \ pmod m $的正确性。我们的工作概括了当$ n $是$ 2 $的电力时使用的Gerbicz-Pietrzak证明计划，并已成功实施了PrimeGrid，使分布式搜索量的效率翻了一番。
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\equiv r\pmod 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.
