Efficient checkers for number-theoretic computations (Q1898116)

Program checkers, as proposed by \textit{M. Blum} [Designing programs to check their work (Tech. Rep., ICSI, UC Berkeley) (1988)], embody a probabilistic approach to the problem of program correctness. Let \(P\) be a given program that purports to compute a function \(\pi\). Each time \(P\) is run on an input \(d\), the checker for \(\pi\) is also run. It interrogates \(P\) with inputs that may differ from \(d\), and produces a decision on the correctness of the result of the call \(P(d)\) that is guaranteed within a small probability of error. The complexity of a checker is a bound for the number of calls to \(P\) it engenders and for the time complexity of the rest of its computation, as a function of the input size \(n\). The present paper describes an efficient checker for the greatest common divisor problem of complexity \(O(1)\), and one for modular exponentiation of complexity \(O(\log n)\). The latter operation is an important one in the RSA cryptosystem. It is also shown that, under a certain hypothesis whose validity is an open problem, an \(O(1)\)-checker for modular exponentiation exists.