RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
Main page
About this project
Software
Classifications
Links
Terms of Use

Search papers
Search references

RSS
Current issues
Archive issues
What is RSS






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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:

Document Type: Article
MSC: 11T06, 11Y16, 68Q25, 94A60
Received: 05.10.2011
Accepted:24.08.2012
Language: English

Linking options:
  • http://mi.mathnet.ru/eng/siamc1

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:44

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019