Correcting noisy exponentiation black-boxes modulo a prime

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)414-417
Number of pages4
JournalInformation Processing Letters
Volume113
Issue number12
DOIs
Publication statusPublished - 2013

Keywords

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

Fingerprint Dive into the research topics of 'Correcting noisy exponentiation black-boxes modulo a prime'. Together they form a unique fingerprint.

Cite this