RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Главная страница
О проекте
Программное обеспечение
Классификаторы
Полезные ссылки
Пользовательское
соглашение

Поиск публикаций
Поиск ссылок

RSS
Текущие выпуски
Архивные выпуски
Что такое RSS






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


SIAM J. Comput., 2012, том 41, выпуск 6, страницы 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

Аннотация: 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.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 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


Реферативные базы данных:

Тип публикации: Статья
MSC: 11T06, 11Y16, 68Q25, 94A60
Поступила в редакцию: 05.10.2011
Язык публикации: английский

Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/siamc1

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:32

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018