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

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

В математиці, особливо в абстрактній алгебрі і її застосуваннях, дискретний логарифмтеоретико-груповий аналог звичайного логарифму. Зокрема, звичайний логарифм 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).

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

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

(1)

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

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

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

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

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

Будемо розв'язувати задачу методом перебору. Випишемо таблицю всіх степенів числа 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] В алгоритмі використовується таблиця, що складається з пар елементів і виконується множень. Цей алгоритм повільний і не придатний для практичного застосування. Для конкретних груп існують ефективніші алгоритми.

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

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

(2)

де  — просте, не ділиться на . Якщо є твірним елементом групи , то рівняння (2) має розв'язок за будь-яких . Такі числа ще відомі як первісні корені, і їх кількість дорівнює , де  — функція Ейлера. Розв'язок рівняння (2) можна знайти по формулі:

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

Наступний алгоритм має складність .

Алгоритм
  1. Присвоїти
  2. Обчислити
  3. Скласти таблицю значень для і відсортувати її.
  4. Скласти таблицю значень для і відсортувати її.
  5. Знайти спільні елементи в таблицях. Для них звідки
  6. Видати .

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

Примітки[ред.ред. код]

  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. 


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