There are no translations available.
On the hidden shifted power problem
(joint work of Jean Bourgain, Moubariz Garaev and Sergei Konyagin)
Igor Shparlinski, Macquarie University
10 de febrero, 2012, 12:00 h., Sala Naranja ICMAT (cartel).
We consider the problem of recovering a hidden element s of a finite field of elements from queries to an oracle that for a given returns for a given divisor . This question is motivated by some applications to pairing based cryptography. Using Largange interpolation one can recover s in time on a classical computer. In the case of an efficient quantum algorithm has been given by W. van Dam, S. Hallgren and L. Ip. We describe some techniques from additive combinatorics and analytic number theory that lead to more efficient classical algorithms than the naive interpolation algorithm, for example, they use substantially fewer queries to the oracle. We formulate some questions and discuss whether quantum algorithms can give further improvement.