|
Труды по дискретной математике, 2006, том 9, страницы 121–151
(Mi tdm144)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Эффективный вариант метода решета числового поля для дискретного логарифмирования в поле
$\mathbf{GF}(p^k)$
Д. В. Матюхин
Аннотация:
В работе изложен алгоритм дискретного логарифмирования в мультипликативной группе поля $\mathbf{GF}(p^k)$, где $p$ – большое простое число, $k$ – фиксировано, являющийся вариантом метода решета числового поля. При некоторых эвристических предположениях доказано, что сложность алгоритма по порядку не превышает
$$
\exp\{[(64/9)^{1/3}+o(1)](\ln p^k)^{1/3}(\ln\ln p^k)^{2/3}\}
$$
двоичных операций, где $o(1)\to0$ при $p\to\infty$, что совпадает с аналогичной оценкой для варианта метода, предложенного О. Широкауэром. Алгоритм, предложенный в настоящей работе, представляется более простым и эффективным с точки зрения практической реализации.
Образец цитирования:
Д. В. Матюхин, “Эффективный вариант метода решета числового поля для дискретного логарифмирования в поле
$\mathbf{GF}(p^k)$”, Тр. по дискр. матем., 9, Гелиос АРВ, М., 2006, 121–151
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tdm144 https://www.mathnet.ru/rus/tdm/v9/p121
|
Статистика просмотров: |
Страница аннотации: | 1312 | PDF полного текста: | 556 |
|