Дискретное логарифмирование (DLOG) — задача обращения функции
в некоторой конечной мультипликативной группе
.
Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.
Для заданных g и a решение x уравнения
называется дискретным логарифмом элемента a по основанию g. В случае, когда G является мультипликативной группой кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.
Пример
Рассмотрим задачу дискретного логарифмирования в кольце вычетов по модулю простого числа. Пусть задано сравнение
|
|
Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 33≡27 — остаток от деления на 17 равен 10).
31 ≡ 3 |
32 ≡ 9 |
33 ≡ 10 |
34 ≡ 13 |
35 ≡ 5 |
36 ≡ 15 |
37 ≡ 11 |
38 ≡ 16 |
39 ≡ 14 |
310 ≡ 8 |
311 ≡ 7 |
312 ≡ 4 |
313 ≡ 12 |
314 ≡ 2 |
315 ≡ 6 |
316 ≡ 1 |
Теперь легко увидеть, что решением рассматриваемого сравнения является x=4, поскольку 34≡13.
На практике модуль обычно является достаточно большим числом, и метод перебора является слишком медленным, поэтому возникает потребность в более быстрых алгоритмах.
Алгоритмы решения
В произвольной мультипликативной группе
Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья J. Buchmann, M. J. Jacobson и E. Teske.[1] В алгоритме используется таблица, состоящая из
пар элементов и выполняется
умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.
В кольце вычетов по простому модулю
Рассмотрим сравнение
|
(2) |
где
— простое,
не делится на
. Если
является образующим элементом группы
, то уравнение (2) имеет решение при любых
. Такие числа
называются ещё первообразными корнями, и их количество равно
, где
— функция Эйлера. Решение уравнения (2) можно находить по формуле:
|
|
Однако, сложность вычисления по этой формуле хуже, чем сложность перебора.
Следующий алгоритм имеет сложность
.
- Алгоритм
- Присвоить
- Вычислить
- Составить таблицу значений
для
и отсортировать её.
- Составить таблицу значений
для
и отсортировать её.
- Найти общие элементы в таблицах. Для них
откуда
- Выдать
.
Существует также множество других алгоритмов для решения задачи дискретного логарифмирования в поле вычетов. Их принято разделять на экспоненциальные и субэкспоненциальные. Полиномиального алгоритма для решения этой задачи пока не существует.
Алгоритмы с экспоненциальной сложностью
- Алгоритм Шенкса (алгоритм больших и малых шагов, baby-step giant-step)
- Алгоритм Полига-Хеллмана — работает, если известно разложение числа
на простые множители. Сложность:
. Если множители, на которые раскладывается
, достаточно маленькие, то алгоритм очень эффективен[2].
- ρ-метод Полларда имеет эвристическую оценку сложности
[3].
Субэкспоненциальные алгоритмы
В L-нотации вычислительная сложность данных алгоритмов оценивается как
арифметических операций, где
и
— некоторые константы. Эффективность алгоритма во многом зависит от близости величин
и
к 1 и 0, соответственно.
- Алгоритм Адлемана появился в 1979 году[4]. Это был первый субэкспоненциалный алгоритм дискретного логарифмирования. На практике он всё же недостаточно эффективен. В этом алгоритме
.
- Алгоритм COS был предложен в 1986 году математиками Копперсмитом (Don Coppersmith), Одлыжко (Andrew Odlyzko) и Шреппелем (Richard Schroeppel)[5]. В этом алгоритме константа
,
. В 1991 году с помощью этого метода было проведено логарифмирование по модулю
. В 1997 году Вебер провел дискретное логарифмирование по модулю
с помощью некоторой версии данного алгоритма. Экспериментально показано, что при
алгоритм COS лучше решета числового поля.
- Дискретное логарифмирование при помощи решета числового поля было применено к дискретному логарифмированию позднее, чем к факторизации чисел. Первые идеи появились в 1990-х годах. Алгоритм, предложенный Д. Гордоном в 1993 году, имел эвристическую сложность
[6], но оказался достаточно непрактичным. Позднее было предложено множество различных улучшений данного алгоритма. Было показано, что при
решето числового поля быстрее, чем COS. Современные рекорды в дискретном логарифмировании получены именно с помощью этого метода.
Наилучшими параметрами в оценке сложности на данный момент является
,
[7].
Для чисел специального вида результат можно улучшить. В некоторых случаях можно построить алгоритм, для которого константы будут
,
. За счёт того, что константа
достаточно близка к 1, подобные алгоритмы могут обогнать алгоритм с
.
В произвольном конечном поле
Задача рассматривается в поле GF(q), где
,
— простое.
- Алгоритм исчисления индексов (index-calculus) эффективен, если
невелико. В этом случае он имеет эвристическую оценку сложности
.
- Алгоритм Эль-Гамаля, появившийся в 1985 году, применим при
и имеет сложность
арифметических операций.
- Алгоритм Копперсмита дискретного логарифмирования в конечном поле характеристики 2 стал первым субэкспоненциальным алгоритмом дискретного логарифмирования с константой
в оценке сложности
. Данный алгоритм появился в 1984 году — до изобретения решета числового поля[8].
В группе точек на эллиптической кривой
Рассматривается группа точек эллиптической кривой над конечным полем. В данной группе определена операция сложения двух точек. Тогда
— это
. Решением задачи дискретного логарифмирования на эллиптической кривой является нахождение такого натурального числа
, что
для заданных точек
и
До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек эллиптической кривой. Впоследствии, Альфред Менезес[en]*, Окамото (Tatsuaki Okamoto) и Скотт Ванстоун[en]* предложили алгоритм, использующий спаривание Вейля[9]. Для эллиптической кривой, определённой над полем
, данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле
. Однако, данное сведение полезно, только если степень
мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.
Примечания
- ↑ Buchmann J., Jacobson M. J., Teske E. (1997). “On some computational problems in finite abelian groups” (PDF). Mathematics of Computation. 66: 1663—1687. DOI:10.1090/S0025-5718-97-00880-6.
- ↑ S. Pohlig, M. Hellman. An improved algorithm for computing logarithms over and its cryptographic significance (Corresp.) // IEEE Transactions on Information Theory. — 1978. — Январь (т. 24, вып. 1). — С. 106–110. — ISSN 0018-9448. — DOI:10.1109/TIT.1978.1055817.
- ↑ J. M. Pollard. Monte Carlo methods for index computation (mod p) // Mathematics of Computation. — 1978. — Январь (т. 32, вып. 143). — С. 918–924. — DOI:10.1090/S0025-5718-1978-0491431-9.
- ↑ L. Adleman. A subexponential algorithm for the discrete logarithm problem with applications to cryptography // 20th Annual Symposium on Foundations of Computer Science. — 1979. — Октябрь. — С. 55–60. — DOI:10.1109/SFCS.1979.2.
- ↑ Don Coppersmith, Andrew M. Odlzyko, Richard Schroeppel. Discrete logarithms inGF(p) (англ.) // Algorithmica. — 1986. — November (vol. 1, iss. 1—4). — P. 1–15. — DOI:10.1007/BF01840433.
- ↑ Daniel M. Gordon. Discrete Logarithms in GF(p) Using the Number Field Sieve // SIAM Journal on Discrete Mathematics. — 1993. — Т. 6, вып. 1. — С. 124–138. — DOI:10.1137/0406010.
- ↑ Don Coppersmith. Modifications to the Number Field Sieve (англ.) // Journal of Cryptology. — 1993. — Vol. 6, iss. 3. — P. 169–180. — DOI:10.1007/BF00198464.
- ↑ D. Coppersmith. Fast evaluation of logarithms in fields of characteristic two // IEEE Transactions on Information Theory. — 1984. — Июль (т. 30, вып. 4). — С. 587–594. — ISSN 0018-9448. — DOI:10.1109/TIT.1984.1056941.
- ↑ A. J. Menezes, T. Okamoto, S. A. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field // IEEE Transactions on Information Theory. — 1993-09-01. — Т. 39, вып. 5. — С. 1639–1646. — ISSN 0018-9448. — DOI:10.1109/18.259647.
- ↑ Diffie, Hellman, 1976.
- ↑ Elgamal, 1984.
- ↑ Elgamal, 1985.
- ↑ James L. Massey, Jimmy K. Omura. Method and apparatus for maintaining the privacy of digital messages conveyed by public transmission (неопр.) (Jan 28, 1986).
- ↑ Shor, 1994.
- ↑ Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // Foundations of Computer Science : Conference Publications. — 1997. — P. 1484–1509.
- ↑ CompuTerra Online #224 — Квантовые компьютеры и квантовые вычисления… Беседа с кандидатом физико-математических наук, специалистом по теории алгоритмов Михаилом Вялым (Вычислительный центр РАН)
Литература
- Diffie W., Hellman M. E. New Directions in Cryptography // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644–654. — ISSN 0018-9448 — doi:10.1109/TIT.1976.1055638
<a href='https://wikidata.org/wiki/Track:Q16194641'></a><a href='https://wikidata.org/wiki/Track:Q27178858'></a><a href='https://wikidata.org/wiki/Track:Q127793'></a><a href='https://wikidata.org/wiki/Track:Q476466'></a><a href='https://wikidata.org/wiki/Track:Q462089'></a>
- Elgamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // Advances in Cryptology — CRYPTO ’84: 4th Annual International Cryptology Conference, Santa Barbara, 1984, Proceedings / George Robert Blakley Jr., D. Chaum — New York, NY, USA: Springer-Verlag New York, 1985. — P. 10–18. — 491 p. — (Lecture Notes in Computer Science; Vol. 196) — ISBN 978-0-387-15658-3 — ISSN 0302-9743 — doi:10.1007/3-540-39568-7_2
<a href='https://wikidata.org/wiki/Track:Q52601238'></a><a href='https://wikidata.org/wiki/Track:Q26883131'></a><a href='https://wikidata.org/wiki/Track:Q5537041'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q26883127'></a><a href='https://wikidata.org/wiki/Track:Q1173973'></a><a href='https://wikidata.org/wiki/Track:Q910915'></a>
- Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1985. — Vol. 31, Iss. 4. — P. 469–472. — ISSN 0018-9448 — doi:10.1109/TIT.1985.1057074
<a href='https://wikidata.org/wiki/Track:Q910915'></a><a href='https://wikidata.org/wiki/Track:Q127793'></a><a href='https://wikidata.org/wiki/Track:Q16194641'></a><a href='https://wikidata.org/wiki/Track:Q52600627'></a>
- Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on — IEEE, 1994. — P. 124–134. — ISBN 0-8186-6580-7 — doi:10.1109/SFCS.1994.365700
<a href='https://wikidata.org/wiki/Track:Q42308002'></a><a href='https://wikidata.org/wiki/Track:Q42308003'></a><a href='https://wikidata.org/wiki/Track:Q370071'></a>
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
- Коблиц Н. Курс теории чисел и криптографии. — Москва: ТВПб, 2001. — 254 с. — ISBN 5-85484-014-6.
- Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // LNCS[en]. — 1984. — Т. 209. — С. 224—316.
- Ю. В. Нестеренко. Глава 4.8. Дискретное логарифмирование // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1.
- Обзор методов вычисления дискретного логарифма (англ.)
- Нечаев В.И. К вопросу о сложности детерминированного алгоритма для дискретного логарифма // Математические заметки. — 1994. — Февраль (т. 55, вып. 2). — С. 91—101.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .