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

В математиці, особливо в абстрактній алгебрі і її застосуваннях, дискретний логарифм — теоретико-груповий аналог звичайного логарифма. Зокрема, звичайний логарифм log_a(b) — це розв'язок рівняння a^x = b у полі дійсних або комплексних чисел. Подібно, якщо g і h елементи зі скінченної циклічної групи G, тоді розв'язок x рівняння g^x = h зветься дискретним логарифмом h за основою g в групі G.

Приклад

Мабуть найпростіше зрозуміти дискретні логарифми в групі (Z_p)^×. Це множина {1, …, p − 1} (класів конгруентності) щодо множення за модулем просте p.

Якщо ми хочемо знайти k-й степінь числа з цієї групи, ми можемо зробити це знайшовши його k-й степінь і вирахувавши остачу від ділення на p. Цей процес називається дискретним піднесенням до степеня. Наприклад, розглянемо (Z₁₇)^×. щоб обчислити 3⁴ в цій групі, ми спершу обчислюємо 3⁴ = 81, і тоді ділимо 81 на 17, отримуючи в залишку 13. Отже в групі (Z₁₇)^× 3⁴ = 13 .

Дискретний логарифм — це просто обернена операція. Наприклад, візьмемо рівняння 3^k ≡ 13 (mod 17) for k. Як показано вище k=4 є розв'язком. Через те що 3¹⁶ ≡ 1 (mod 17), також випливає, що якщо n ціле, тоді 3^{4+16 n} ≡ 13 × 1ⁿ ≡ 13 (mod 17). Звідси, рівняння має нескінченно багато розв'язків у вигляді 4 + 16n. Більше того, тому що 16 є найменшим додатнім цілим m, що задовільняє 3^m ≡ 1 (mod 17), тобто 16 — це показник 3 в (Z₁₇)^×, це єдині розв'язки. Тотожно, Розв'язок можна виразити як k ≡ 4 (mod 16).

Постановка задачі

Нехай в деякій скінченній мультиплікативній абелевій групі ${\displaystyle G}$ задане рівняння

${\displaystyle g^{x}=a.}$ (1)

Розв'язок задачі дискретного логарифмування полягає в віднайдені деякого цілого невід'ємного числа ${\displaystyle x}$, яке задовольняє рівнянню (1). Якщо воно розв'язне, в нього повинно бути хоча б один натуральний розв'язок, що не перевищує порядок групи. Це одразу грубо оцінює складність алгоритму пошуку розв'язків з гори — алгоритм повного перебору, покрокового піднесення бази до наступного степеня (англ. trial multiplication), вимагає час виконання лінійний до розміру групи ${\displaystyle G}$ і отже, показниково залежить від кількості цифр в розмірі групи. Існує дієвий квантовий алгоритм.

Найчастіше розглядається випадок, коли ${\displaystyle G=\langle g\rangle }$, тобто циклічна, породжена елементом ${\displaystyle g}$. В такому разі рівняння завжди має розв'язок. У випадку довільної групи питання розв'язності задачі дискретного логарифмування вимагає окремого розгляду.

Приклад

Найпростіше розглянути задачу дискретного логарифмування в кільці класів рівності за модулем простого числа.

Нехай дано порівняння

${\displaystyle 3^{x}\equiv 13{\pmod {17}}.}$

Будемо розв'язувати задачу методом перебору. Випишемо таблицю всіх степенів числа 3. Кожен раз ми обчислюємо остачу від ділення на 17 (наприклад, 3³≡27 — остача від ділення на 17 дорівнює 10).

3^1 ≡ 3	3^2 ≡ 9	3^3 ≡ 10	3^4 ≡ 13	3^5 ≡ 5	3^6 ≡ 15	3^7 ≡ 11	3^8 ≡ 16
3^9 ≡ 14	3^10 ≡ 8	3^11 ≡ 7	3^12 ≡ 4	3^13 ≡ 12	3^14 ≡ 2	3^15 ≡ 6	3^16 ≡ 1

Зараз легко побачити, що розв'язком порівняння є x=4, оскільки 3⁴≡13.

Зазвичай, на практиці модуль є досить великим числом, щоб метод повного перебору виявився занадто повільним, тому виникає потреба у швидших алгоритмах.

Алгоритми розв'язання

У довільній мультиплікативній групі

Розв'язності задачі дискретного логарифмування у довільній скінченній абелевій групі присвячена стаття J. Buchmann, M. J. Jacobson і E. Teske. В алгоритмі використовується таблиця, що складається з ${\displaystyle O({\sqrt {|\langle g\rangle |}})}$ пар елементів і виконується ${\displaystyle O({\sqrt {|\langle g\rangle |}})}$ множень. Цей алгоритм повільний і не придатний для практичного застосування. Для конкретних груп існують ефективніші алгоритми.

У кільці лишків за простим модулем

Розглянемо порівняння

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

(2)

де ${\displaystyle p}$ — просте, ${\displaystyle b}$ не ділиться на ${\displaystyle p}$. Якщо ${\displaystyle a}$ це твірний елемент групи ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$, то рівняння (2) має розв'язок за будь-яких ${\displaystyle b}$. Такі числа ${\displaystyle a}$ ще відомі як первісні корені, і їх кількість дорівнює ${\displaystyle \phi (p)=p-1}$, де ${\displaystyle \phi }$ — функція Ейлера. Розв'язок рівняння (2) можна знайти по формулі:

${\displaystyle x\equiv \sum \limits _{i=1}^{p-2}(1-a^{i})^{-1}b^{i}{\pmod {p}}.}$

Однак, складність обчислення за цією формулою гірше ніж складність перебирання.

Наступний алгоритм має складність ${\displaystyle O({\sqrt {p}}\cdot \log {p})}$.

Алгоритм

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

Існує також багато інших алгоритмів для розв'язання задачі дискретного логарифмування у полі лишків. Їх прийнято розділяти на експоненційні і субекспоненційні. Поліноміального алгоритму для розв'язання цієї задачі не існує.

Див. також

• Дискретне логарифмування на еліптичній кривій

Примітки

1. Shor, Peter (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing. 26 (5): 1484—1509. arXiv:quant-ph/9508027.
2. Buchmann J., Jacobson M. J., Teske E. (1997). (PDF). Mathematics of Computation. 66: 1663—1687. doi:10.1090/S0025-5718-97-00880-6. Архів оригіналу (PDF) за 4 березня 2016. Процитовано 4 березня 2016.