EFFICIENT CHECKERS FOR NUMBER-THEORETIC COMPUTATIONS

Blum has recently proposed a new approach to the problem of program co rrectness, the program checker. Here, efficient program checkers are p resented for two important number theory problems, integer GCD and mod ular exponentiation. The former result answers an open problem posed b y Blum. The latter result paves the way for more robust cryptographic programs, as modular exponentiation is the basis for several cryptosys tems. Taken together, these results lay the foundation for more reliab le number-theoretic programs. (C) 1995 Academic Press. Inc.