## Abstract

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εZ outputs some tεZ with ^{gu}≡t+z(modp), where |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.

Original language | English |
---|---|

Pages (from-to) | 414-417 |

Number of pages | 4 |

Journal | Information Processing Letters |

Volume | 113 |

Issue number | 12 |

DOIs | |

Publication status | Published - 2013 |

## Keywords

- analysis of algorithms
- noisy exponentiation
- congruences
- concentration of solutions