SIAM Journal on Computing
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB

 SIAM J. Comput., 2012, Volume 41, Issue 6, Pages 1524–1557 (Mi siamc1)

On the hidden shifted power problem

J. Bourgaina, M. Z. Garaevb, S. V. Konyaginc, I. E. Shparlinskid

a Institute for Advanced Study, Princeton, NJ 08540, United States
b Centro de Ciencias Matemáticas, Universidad Nacional Autónoma de México, C.P. 58089, Morelia, Michoacán, Mexico
c Steklov Mathematical Institute, Moscow, 119991, Russian Federation
d Department of Computing, Macquarie University, Sydney, NSW 2109, Australia

Abstract: We consider the problem of recovering a hidden element $s$ of a finite field $\mathbb{F}_q$ of $q$ elements from queries to an oracle that for a given $x \in \mathbb{F}_q$ returns $(x+s)^e$ for a given divisor $e \mid 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.

 Funding Agency Grant Number Russian Foundation for Basic Research 11-01-00329 Australian Research Council DP1092835 National Science Foundation DMS-0808042 This author's research was supported by Russian Fund for Basic Research grant 11-01-00329. This author's research was supported by Australian Research Council grant DP1092835. This author's research was partially supported by National Science Foundation grant DMS-0808042.

DOI: https://doi.org/10.1137/110850414

Bibliographic databases:

MSC: 11T06, 11Y16, 68Q25, 94A60
Accepted:24.08.2012
Language: