Type: Article

On the hidden shifted power problem

Bourgain, Jean; Garaev, Moubariz Z.; Konyagin, Sergei V.; et al.;

Abstract:

We consider the problem of recovering a hidden element s of a finite field F-q of q elements from queries to an oracle that for a given x is an element of F-q returns (x + s)(e) for a given divisor e vertical bar q - 1. We use some techniques from additive combinatorics and analytic number theory that lead to more efficient algorithms than the naive interpolation algorithm; for example, they use substantially fewer queries to the oracle.