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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Приклад[ред.ред. код]

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

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

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

Постановка задачі[ред.ред. код]

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

g^x=a. (1)

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

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

Приклад[ред.ред. код]

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

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

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

Будемо розв'язувати задачу методом перебору. Випишемо таблицю всіх степенів числа 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.[2] В алгоритмі використовується таблиця, що складається з O(\sqrt{|\langle g\rangle|}) пар елементів і виконується O(\sqrt{|\langle g\rangle|}) множень. Цей алгоритм повільний і не придатний для практичного застосування. Для конкретних груп існують ефективніші алгоритми.

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

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

a^x\equiv b\pmod{p}, (2)

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

x\equiv\sum\limits_{i=1}^{p-2}(1-a^i)^{-1}b^i\pmod{p}.

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

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

Алгоритм
  1. Присвоїти H:=\left\lfloor \sqrt{p}\right\rfloor + 1
  2. Обчислити c= a^H\bmod{p}
  3. Скласти таблицю значень c^u\bmod{p} для 1\leq u\leq H і відсортувати її.
  4. Скласти таблицю значень b\cdot a^v\bmod{p} для 0\leq v\leq H і відсортувати її.
  5. Знайти спільні елементи в таблицях. Для них c^u\equiv b\cdot a^v\pmod{p}, звідки a^{Hu-v}\equiv b\pmod{p}.
  6. Видати 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). On some computational problems in finite abelian groups. Mathematics of Computation 66. с. 1663–1687. doi:10.1090/S0025-5718-97-00880-6. 


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.