Приведенный алгоритм хуже по значению константы
L
n
1
/
2
,
√
3
, но,
тем не менее, субэкспоненциальный. Также недостатком является требова-
ние к памяти
L
n
[1
/
2
,
1
,
15]
. В то же время он прост, не требует каких-либо
специальных стратегий и дополнительных алгоритмов, основан на элемен-
тарных операциях.
Возможно, описанные подходы найдут применение при логарифмиро-
вании в некоторых других группах, например, группе точек эллиптической
кривой. Выделение общих “множителей” в паре точек вполне может иметь
место. А потому может оказаться полезной техника построения последова-
тельностей на отображении Ньютона.
Автор благодарит А.Н. Лебедева и Г.А. Лебедева за содействие в разра-
ботке алгоритмов и написании настоящей работы, полезные замечания и
обсуждения.
ЛИТЕРАТУРА
1.
Pohlig S.C.
,
Hellman M.E.
An Improved Algorithm for Computing Logarithms Over
GF(p) and its Cryptographic Significance // IEEE, Transactions on Information
Theory. 1978. Vol. 1. No. 24. P. 106–110.
2.
Shanks D.
The infrastructure of a real quadratic field and its applications //
Proceedings of the Number Theory Conference. University of Colorado, Boulder.
1972. P. 217–224.
3.
Глухов М.М.
,
Круглов И.А.
,
Пичкур А.Б.
,
Черемушкин А.В.
Введение в теоретико-
числовые методы криптографии. СПб.: Лань, 2011. 400 с.
4.
Pollard J.M.
Monte Carlo methods for index computation (mod p) // Math. Comp.
1978. No. 32. P. 918–924.
5.
Adleman L.M.
A subexponentional algorithm for the discrete logarithm problem with
applications to cryptography. Proceedings of the IEEE 20th Annual Symposium on
Foundations of Computer Science. 1979. P. 55–60.
6.
Dixon J.D.
Asymptotically fast factorization of integers // Math. Comp. 36 (153).
1981. P. 255–260.
7.
De Bruijn N.G.
,
Erd¨os P.
A combinatioral [sic] problem // Indagationes Mathematica.
Vol. 10. 1948. P. 421–423.
8.
Василенко О.Н.
Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО.
2003. 328 с.
9.
Матюхин Д.В.
Об асимптотической сложности дискретного логарифмирования
в поле GF(p) // Дискретная математика. 2003. Т. 15. Вып. 1. С. 28–49.
10.
Coppersmith D.
,
Odlyzko A.M.
,
Schroeppel R.
Discrete logarithms in GF(p).
Algorithmica. 1986. Vol. 1. P. 1–15.
REFERENCES
[1] Pohlig S.C., Hellman M.E. An Improved Algorithm for Computing Logarithms Over
GF(p) and its Cryptographic Significance.
IEEE, Transactions on Information Theory
,
1978, vol. 1, no. 24, pp. 106–110.
[2] Shanks D. The infrastructure of a real quadratic field and its applications. Proc.
Number Theory Conference. Un. of Colorado, Boulder, 1972. pp. 217–224.
[3] Glukhov M.M., Kruglov I.A., Pichkur A.B., Cheremushkin A.V. Vvedenie v
teoretiko-chislovye metody kriptografii [Introduction to number-theoretic methods
of cryptography]. SPb., Lan’ Publ., 2011. 400 p.
94 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
