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.