Реферат на тему:

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

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

Означення. Нехай G – скінченна циклічна група порядка n. Нехай g –
генератор G та b ??G. Дискретним логарифмом числа b за основою g
називається таке число x (0 ??x ??n — 1), що gx = b та позначається x =
loggb.

Проблема дискретного логарифму. Нехай p – просте число, g – генератор
множини Zp*, y ? Zp*. Знайти таке значення x (0 ? x ? p — 2), що gx ? y
(mod p). Число x називається дискретним логарифмом числа y за основою g
та модулем p.

Узагальнена проблема дискретного логарифму. Нехай G – скінченна циклічна
група порядка n, g – її генератор, b ??G. Необхідно знайти таке число x
(0 ??x ??n — 1), що gx = b.

Розширенням узагальненої проблеми може стати задача розв’язку рівняння
gx = b, коли знято умову циклічності групи G, а також умову того, що g –
генератор G (в такому випадку рівняння може і не мати розв’язку).

Приклад. g = 3 є генератором Z7*: 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 =
5, 36 = 1.

log34 = 4 (mod 7), тому що розв’язком рівняння 3x = 4 буде x = 4.

Теорема. Нехай а – генератор скінченної циклічної групи G порядка n.
Якщо існує алгоритм, який обчислює дискретний логарифм за основою а, то
цей алгоритм може також обчислити дискретний логарифм за будь-якою
основою b, яка є генератором G.

Доведення. Нехай k ? G, x = logak, y = logbk, z = logab. Тоді ax = by =
(az)y, звідки x = zy mod n. Підставимо в останню рівність замість
змінних логарифмічні вирази:

logak =(logab) (logbk) mod n

або

logbk =(logak) (logab)-1 mod n.

З останньої рівності випливає справедливість теореми.

Примітивний алгоритм

Для знаходження loggb (g – генератор G порядка n, b ??G) будемо
обчислювати значення g, g2, g3, g4, … поки не отримаємо b. Часова
оцінка алгоритму – O(n). Якщо n – велике число, то час обчислення
логарифму є достатньо великим і тому алгоритм є неефективним.

Алгоритм великого та малого кроку

Першим детермінованим алгоритмом для обчислення дискретного логарифму
був алгоритм великого та малого кроку, запропонований Шанком (Shank)
[1].

Для обчислення loggb в групі Zn* необхідно зробити наступні кроки:

???;

(за модулем n);

3. Побудувати список L2 = b, bg, bg2, …, bga — 1 (за модулем n);

4. Знайти число z, яке зустрілося в L1 та L2.

Тоді z = bgk = gla для деяких k та l. Звідси b = gla — k = gx; x = la —
k.

Два питання постає при дослідженні роботи наведеного алгоритму:

1. Чи завжди знайдеться число, яке буде присутнім в обох списках?

2. Як ефективно знайти значення z?

Запишемо x = sa + t для деяких s, t таких що 0 ? s, t < a. Тоді b = gx = gsa + t. Домножимо рівність на ga - t, отримаємо: bga - t = gs(a + 1). Значення зліва обов’язково зустрінеться в L2, а справа – в L1. Відсортуємо отримані списки L1 та L2 за час O(a * log a). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z знайдене, якщо ні – то видалити менше число і продовжити перевірку. Приклад. Розв’язати рівняння: 2x ? 11 (mod 13). ?? = 4; L1: 1, 24 ? 3, 28 ? 9, 212 ? 1, 216 ? 3; L2: 11, 11 * 2 ? 9, 11 * 22 ? 5, 11 * 23 ? 10; Число 9 зустрілося в обох списках. 11 * 2 ? 28, 11 ? 27, звідки x = 7. Відповідь: x = 7. ???, 0 ? s, t < a) переписати у вигляді b * (g-a)s = gt. Обчислимо g-a та складемо таблицю значень gt, 0 ? t < a. Далі починаємо знаходити значення b * (g-a)s, s = 0, 1, … перевіряючи їх наявність у таблиці gt. Як тільки знаходяться такі s та t, алгоритм зупиняється. Приклад. Обчислити log23 в групі Z19* . ?? = 5: t 0 1 2 3 4 2t 1 2 4 8 16 2-1 ? 10 (mod 19), оскільки 2 * 10 ? 1 (mod 19). Тоді 3 * (2-5)s (mod 19) ? 3 * (105)s (mod 19) ? 3 * 3s (mod 19) Обчислюємо 3 * 3s, s = 0, 1, … : s 0 1 2 3 * 3s 3 9 8 Значення 8, яке отримали при s = 2, присутнє в таблиці 2t, 0 ? t < 5. Звідси 3 * (2-5)2 = 23 або 3 = (25)2 * 23 = 25*2+3 = 213. Відповідь: 3 = 213, тобто log23 = 13. Алгоритм Полард - ро Нехай G – циклічна група з порядком n (n – просте). Розіб’ємо елементи групи G на три підмножини S1, S2 та S3, які мають приблизно однакову потужність. При цьому необхідне виконання умови: 1 ??S2. Визначимо послідовність елементів xi наступним чином: , i ??0 (1) Ця послідовність у свою чергу утворить дві послідовності ci та di , що задовольняють умові та визначаються наступним чином: , i ??0 (2) та , i ??0 (3) . Логарифмуючи останню рівність за основою a, матимемо: (di - d2i) * logab ??(c2i - ci) mod n Якщо di ? d2i (mod n), то це рівняння може бути ефективно розв’язано для обчислення logab. Алгоритм Вхід: генератор a циклічної групи G з порядком n та елемент b ??G. Вихід: дискретний логарифм x = logab. 1. x0 ??1, c0 ??0, d0 ??0. 2. for i = 1, 2, ... do 2.1. За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3). 2.2. if (xi = x2i) then r ??(di - d2i) mod n; if (r = 0) then return (FALSE); // розв’язку не знайдено x ? r -1 (ci - c2i) mod n. return (x). . Приклад. Обчислити log29 в групі Z19*. Побудуємо наступну таблицю значень послідовностей xi, ci, di: i xi ai bi x2i a2i b2i 1 9 0 1 18 1 1 2 18 1 1 4 4 2 3 17 2 1 4 8 6 4 4 4 2 4 16 14 5 17 4 3 4 32 30 6 4 8 6 4 64 62 На 6 кроці отримали x6 = x12 . Підставивши їх значення, отримаємо: 28 * 96 = 264 * 962 або 28 – 64 = 962 – 6 , 2-56 = 956 Логарифмуємо рівність: -56 * log29 = 56 (mod 18), оскільки |Z19*| = 18. Враховуючи що -56 (mod 18) ??16, 56 (mod 18) ??2, перепишемо рівність у вигляді 16 * log29 = 2 (mod 18) або 8 * log29 = 1 (mod 9). log29 = 8-1 (mod 9) = 8. Відповідь: log29 = 8. Індексний алгоритм Алгоритм, базований на обчисленні індексів, є найпотужним при обчисленні дискретного логарифму. Необхідно побудувати відносно невелику підмножину S елементів групи G, яка називається множниковою основою. Ця підмножина повинна обиратися таким чином, щоб як можна більша частина елементів G могла бути представлена у вигляді добутку її елементів. При обчисленні значення logab (a – генератор G, b ??G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b. Алгоритм Вхід: генератор a циклічної групи G порядка n та елемент b ??G. Вихід: дискретний логарифм x = logab. 1. Побудувати множину S – множникову основу. Нехай S = {p1, p2, …, pt}. В якості значень pi можна обрати, наприклад, i - те просте число. 2. Побудувати систему лінійних рівнянь, розв’язком якої будуть значення logapi. Для цього виконаємо наступні кроки: 2.1. Обрати деяке ціле k, 0 ??k ??n - 1 та обчислити ak . 2.2. Спробувати представити значення ak у вигляді добутку чисел з S: , ci ??0 Якщо така рівність знайдена, то записати рівняння: (mod n) 2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + c лінійних рівнянь. Невелике ціле число c (1 ? c ? 10) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку). 3. Розв’язати утворену систему рівнянь, отримати значення logapi, 1? i ? t. 4. Обчислення logab. 4.1. Обрати деяке ціле k, 0 ??k ??n - 1 та обчислити b * ak . 4.2. Спробувати представити значення b * ak у вигляді добутку чисел з S: , di ??0 Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо: - k) mod n Приклад. Обчислити log212 в групі Z19*. 1. Нехай S = {2, 3, 5} – множникова основа. 2. Будуємо систему рівнянь для знаходження значень log2pi, де pi ??S. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння. k = 5: 25 (mod 19) ? 13 – не представимо у вигляді добутку чисел з S. k = 7: 27 (mod 19) ? 14 – не представимо у вигляді добутку чисел з S. k = 2: 22 (mod 19) ? 4 = 22. Перше рівняння: 2 = 2log22. k = 10: 210 (mod 19) ? 17 – не представимо у вигляді добутку чисел з S. k = 15: 215 (mod 19) ? 12 = 22 * 3. Друге рівняння: 15 = 2log22 + log23. k = 11: 211 (mod 19) ? 15 = 3 * 5. Третє рівняння: 11 = log23 + log25. 3. Система рівнянь за модулем 18 (порядок Z19* дорівнює 18) має вигляд: Її розв’язком буде: log22 = 1, log23 = 13, log25 = 16 4. Обчислення log212. k = 3: 12 * 23 (mod 19) ? 1 – не представимо у вигляді добутку чисел з S. k = 7: 12 * 27 (mod 19) ? 16 = 24. log212 + 7 ? 4log22 (mod 18), log212 ? (4log22 – 7) (mod 18) = 15. Відповідь: log212 = 15. Алгоритм Поліга – Хелмана Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники. Нехай g, h ? G, |G| = ps, p – просте. Тоді значення x = loggh можна подати у вигляді: x = x0 + x1p + x2p2 + … + xs-1ps-1 Піднесемо рівняння h = gx до степеня ps-1: = , = 1 (g – генератор групи, ps – її порядок). знаходимо x0. Далі маючи значення x0, x1, …, xi-1 можна обчислити xi з рівняння Приклад. Обчислити log37 в Z17*. Необхідно розв’язати рівняння 3x = 7 в групі, порядок якої дорівнює 16 = 24. Представимо x у двійковій системі числення: x = x0 + 2x1 + 4x2 + 8x3. 1. Обчислення x0. Піднесемо рівняння 3x = 7 до степеня 23 = 8: = -1, = -1. = -1, x0 = 1. 2. Обчислення x1. = 3-1 (mod 17) = 6, отримаємо: = 8. = -1, x1 = 1. 3. Обчислення x2. 1. D. Shanks. Class number, a theory of factorization and genera. In Proc. Symposium Pure Mathematics, vol.20, pp.415-440. American Mathematical Society, 1970.

Похожие записи