Дискретное логарифмирование

Универсальные алгоритмы используют только групповую операцию и не зависят от способа представления элементов группы. К ним относятся алгоритм Шенкса (${\displaystyle O({\sqrt {n}})}$ операций и столько же памяти, где ${\displaystyle n=\operatorname {ord} g}$), ρ-метод Полларда (эвристическая оценка ${\displaystyle O({\sqrt {n}})}$ операций при малом объёме памяти)^[3] и алгоритм Полига — Хеллмана, сводящий задачу к подгруппам простого порядка^[4]. Для группы простого порядка ${\displaystyle N}$ любому универсальному алгоритму для получения ответа с заметной вероятностью требуется ${\displaystyle \Omega ({\sqrt {N}})}$ групповых операций^[5]. Поэтому сложность универсальных методов определяется наибольшим простым делителем порядка группы.

В конечных абелевых группах Бухман, Якобсон и Теске предложили варианты алгоритма Шенкса, сложность и объём памяти которых определяются фактическим порядком элемента или значением логарифма, а не заранее известной верхней оценкой порядка группы; алгоритмы реализованы, в частности, для групп классов мнимых квадратичных порядков^[6].

Для конкретных групп существуют алгоритмы, использующие их строение; они рассмотрены ниже.

Рассмотрим сравнение

${\displaystyle g^{x}\equiv a{\pmod {p}},}$

(2)

где ${\displaystyle p}$ — простое, ${\displaystyle a}$ не делится на ${\displaystyle p}$. Мультипликативная группа ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ циклическая порядка ${\displaystyle p-1}$. Если ${\displaystyle g}$ — её образующий элемент, то есть первообразный корень по модулю ${\displaystyle p}$, то сравнение (2) имеет решение при любом ${\displaystyle a}$, не делящемся на ${\displaystyle p}$. Число первообразных корней по модулю ${\displaystyle p}$ равно ${\displaystyle \varphi (p-1)}$, где ${\displaystyle \varphi }$ — функция Эйлера^[7].

Применительно к сравнению (2) алгоритм Шенкса выглядит так. Его сложность — ${\displaystyle O({\sqrt {p}})}$ групповых операций и ${\displaystyle O({\sqrt {p}}\log p)}$ битовых операций при памяти порядка ${\displaystyle {\sqrt {p}}}$.

Алгоритм

1. Присвоить ${\displaystyle H:=\left\lfloor {\sqrt {p}}\right\rfloor +1}$.
2. Вычислить ${\displaystyle c=g^{H}{\bmod {p}}}$.
3. Составить таблицу значений ${\displaystyle c^{u}{\bmod {p}}}$ для ${\displaystyle 1\leq u\leq H}$ и отсортировать её.
4. Составить таблицу значений ${\displaystyle a\cdot g^{v}{\bmod {p}}}$ для ${\displaystyle 0\leq v<H}$ и отсортировать её.
5. Найти общие элементы в таблицах. Для них ${\displaystyle c^{u}\equiv a\cdot g^{v}{\pmod {p}}}$, откуда ${\displaystyle g^{Hu-v}\equiv a{\pmod {p}}}$.
6. Выдать ${\displaystyle Hu-v}$.

Общий элемент существует, так как любое целое ${\displaystyle x}$ из отрезка ${\displaystyle [1,p-1]}$ представимо в виде ${\displaystyle x=Hu-v}$, где ${\displaystyle 1\leq u\leq H}$, ${\displaystyle 0\leq v<H}$ (поскольку ${\displaystyle H^{2}>p}$).

Для группы ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ известны также алгоритмы, использующие арифметику кольца вычетов (метод исчисления индексов); их сложность субэкспоненциальна. Полиномиальных алгоритмов для классических компьютеров не найдено.

1. Алгоритм Шенкса (алгоритм больших и малых шагов, baby-step giant-step);
2. Алгоритм Полига — Хеллмана — работает, если известно разложение числа ${\displaystyle p-1=\prod \limits _{i=1}^{s}q_{i}^{\alpha _{i}}}$ на простые множители. Сложность: ${\displaystyle O(\sum \limits _{i=1}^{s}\alpha _{i}(\log {p}+q_{i}))}$. Если множители, на которые раскладывается ${\displaystyle p-1}$, достаточно маленькие, то алгоритм очень эффективен^[8];
3. ρ-метод Полларда имеет эвристическую оценку сложности ${\displaystyle O(p^{\frac {1}{2}})}$^[9].

Для субэкспоненциальных алгоритмов дискретного логарифмирования в L-нотации вычислительная сложность оценивается как ${\displaystyle L_{p}[d,c]}$ арифметических операций, где ${\displaystyle c>0}$ и ${\displaystyle 0<d<1}$ — некоторые константы. Чем меньше ${\displaystyle d}$, тем медленнее растёт сложность с ростом ${\displaystyle p}$ (то есть тем лучше алгоритм); при равных ${\displaystyle d}$ сравнивают ${\displaystyle c}$ — меньшему значению соответствует меньшая сложность.

1. Алгоритм Адлемана появился в 1979 году^[10]. Это был первый субэкспоненциальный алгоритм дискретного логарифмирования. На практике он всё же недостаточно эффективен. В этом алгоритме ${\displaystyle d={\frac {1}{2}}}$.
2. Алгоритм COS был предложен в 1986 году математиками Копперсмитом (Don Coppersmith), Одлыжко (Andrew Odlyzko) и Шреппелем (Richard Schroeppel)^[11]. В этом алгоритме константа ${\displaystyle c=1}$, ${\displaystyle d={\frac {1}{2}}}$. В 1991 году с помощью этого метода было проведено логарифмирование по модулю ${\displaystyle p\approx 10^{58}}$. В 1997 году Вебер провёл дискретное логарифмирование по модулю ${\displaystyle p\approx 10^{85}}$ с помощью некоторой версии данного алгоритма. Экспериментально показано, что при ${\displaystyle p\leq 10^{90}}$ алгоритм COS лучше решета числового поля.

Решето числового поля было применено к дискретному логарифмированию позже, чем к факторизации целых чисел. Алгоритм, предложенный Д. Гордоном в 1993 году, имел эвристическую сложность ${\displaystyle L_{p}\left[{\tfrac {1}{3}},3^{2/3}\right]}$^[12], однако на практике оказался неэффективен. Последующие улучшения привели к современным вариантам решета числового поля. При ${\displaystyle p\geq 10^{100}}$ они превосходят по скорости алгоритм Копперсмита — Одлыжко — Шреппеля; все современные рекорды дискретного логарифмирования по простому модулю получены именно этим методом. Наилучшими параметрами в оценке сложности являются ${\displaystyle c=(92+26{\sqrt {13}})^{\frac {1}{3}}/3\approx 1{,}902}$, ${\displaystyle d={\frac {1}{3}}}$^[13].

Для простых чисел специального вида — тех, которые можно представить в форме ${\displaystyle p=r^{e}\pm s}$ с небольшим ${\displaystyle s}$, — существует специализированный алгоритм, сложность которого оценивается как ${\displaystyle L_{p}\left[{\tfrac {2}{5}},c\right]}$ с константой ${\displaystyle c\approx 1{,}00475}$^[14]. Хотя показатель ${\displaystyle d=2/5}$ здесь больше, чем ${\displaystyle d=1/3}$ у алгоритмов общего назначения, константа ${\displaystyle c}$ настолько близка к 1, что при достаточно больших ${\displaystyle p}$ такой алгоритм может оказаться быстрее.

Задача рассматривается в поле GF(q), где ${\displaystyle q=p^{n}}$, ${\displaystyle p}$ — простое.

1. Алгоритм исчисления индексов (index-calculus) эффективен, если ${\displaystyle p}$ невелико. В этом случае он имеет эвристическую оценку сложности ${\displaystyle L_{p}\left[{\tfrac {1}{2}},c\right]}$.
2. Алгоритм Эль-Гамаля, появившийся в 1985 году, применим при ${\displaystyle n=2}$ и имеет сложность ${\displaystyle L_{p}\left[{\tfrac {1}{2}},c\right]}$ арифметических операций.
3. Алгоритм Копперсмита дискретного логарифмирования в конечном поле характеристики 2 стал первым субэкспоненциальным алгоритмом дискретного логарифмирования с константой ${\displaystyle d={\frac {1}{3}}}$ в оценке сложности ${\displaystyle L_{p}[d,c]}$. Данный алгоритм появился в 1984 году — до изобретения решета числового поля^[15].

Рассматривается группа точек эллиптической кривой над конечным полем. В данной группе определена операция сложения двух точек. Тогда ${\displaystyle mP}$ — это _{${\displaystyle \underbrace {P+\ldots +P} \limits _{m}}$}. Решением задачи дискретного логарифмирования на эллиптической кривой является нахождение такого натурального числа ${\displaystyle m}$, что ${\displaystyle mP=A}$ для заданных точек ${\displaystyle P}$ и ${\displaystyle A.}$

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек эллиптической кривой. Впоследствии Альфред Менезес, Тацуаки Окамото и Скотт Ванстоун предложили алгоритм, использующий спаривание Вейля^[16]. Для эллиптической кривой, определённой над полем ${\displaystyle GF(q)}$, данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле ${\displaystyle GF(q^{k})}$, где ${\displaystyle k}$ — наименьшее число, для которого порядок точки ${\displaystyle P}$ делит ${\displaystyle q^{k}-1}$ (степень вложения). Однако данное сведение полезно, только если степень ${\displaystyle k}$ мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.