Correcting noisy exponentiation black-boxes modulo a prime

• Improvement of the previously known algorithm of Howgrave-Graham, Nguyen and Shparlinski for correcting noisy modular exponentiation.
• Using a result of Bourgain, Glibichuk and Konyagin, on bounds of character sums over small multiplicative subgroups of finite fields.
• Using some combinatorial arguments to amplify the uniformity of distribution of exponential functions.

We consider the problem of correcting a Δ-noisy exponentiation black-box modulo a prime p, that is, a black-box that, for a fixed integer g  , on input u∈Zu∈Z outputs some t∈Zt∈Z with gu≡t+z(modp), where |z|⩽Δ|z|⩽Δ. N.A. Howgrave-Graham, P.Q. Nguyen and I.E. Shparlinski [Math. Comp. 72 (2003) 1473–1485], give an algorithm for this problem which works in a certain range of Δ and τ, which is a multiplicative order of g modulo p. Here we extend quite substantially the range of τ   and Δ for which this algorithm recovers gx(modp) in probabilistic polynomial time. This improvement is based on a bound of Bourgain, Glibichuk and Konyagin [J. Lond. Math. Soc. 73 (2006) 380–398] on character sums over small multiplicative subgroups of finite fields and some combinatorial arguments.