RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2013, том 25, выпуск 4, страницы 41–53 (Mi dm1256)

О существовании и числе стационарных точек дискретного логарифма по основанию, отличному от первообразного корня

В. В. Астахов


Аннотация: В связи с атаками на системы цифровой подписи возникает задача решения уравнения $x\equiv R^{x+c}(\mathrm{mod}\,p)$, $p$ – простое. В данной работе рассматривается задача о числе и существовании решений $(x,R)$ этого уравнения с ограничениями $0<x<p$, $R\in Z_p^*\setminus\{1\}$, $\mathrm{ord}\,R=d$, $d|p-1$, $d$ – простое. Показано существование таких пар при фиксированном $c$ при $d>\frac{\log_2\,p}{\log_2\log_2p}\cdot(1+\varepsilon(p,c))$, $\varepsilon(p,c)=o(1)$, $p\to\infty$. Также доказано, что решения существуют для всех $c$ при $d>\log_2p\cdot(1+\varepsilon(p))$, $\varepsilon(p)=o(1)$, $p\to\infty$, а число таких решений не меньше $\left[\frac{d-1}{2\cdot(\log_2p+\log_2\log_2p+3)}\right]$ для любых $c,d$ и $p$.

УДК: 511.212

Статья поступила: 18.06.2013

DOI: 10.4213/dm1256


 Англоязычная версия: Discrete Mathematics and Applications, 2014, 24:2, 61–71

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


© МИАН, 2024