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

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

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

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

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

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

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

Приклад. g = 3 є генератором Z₇*: 3¹ = 3, 3² = 2, 3³ = 6, 3⁴ = 4, 3⁵ = 5, 3⁶ = 1.

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

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

Доведення. Нехай k  G, x = log_ak, y = log_bk, z = log_ab. Тоді a^x = b^y = (a^z)^y, звідки x = zy mod n. Підставимо в останню рівність замість змінних логарифмічні вирази:

log_ak =(log_ab) (log_bk) mod n

або

log_bk =(log_ak) (log_ab)^-1 mod n.

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

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

Для знаходження log_gb (g – генератор G порядка n, b G) будемо обчислювати значення g, g², g³, g⁴, ... поки не отримаємо b. Часова оцінка алгоритму – O(n). Якщо n – велике число, то час обчислення логарифму є достатньо великим і тому алгоритм є неефективним.

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

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

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

1. Обчислити a = ;

2. Побудувати список L₁ = 1, g^a, g^2a, ..., g (за модулем n);

3. Побудувати список L₂ = b, bg, bg², ..., bg^{a - 1} (за модулем n);

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

Тоді z = bg^k = g^la для деяких k та l. Звідси b = g^{la - k} = g^x; x = la - k.

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

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

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

Запишемо x = sa + t для деяких s, t таких що 0  s, t < a. Тоді b = g^x = g^{sa + t}. Домножимо рівність на g^{a - t}, отримаємо: bg^{a - t} = g^{s(a + 1)}. Значення зліва обов’язково зустрінеться в L₂, а справа – в L₁.

Відсортуємо отримані списки L₁ та L₂ за час O(a * log a). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z знайдене, якщо ні – то видалити менше число і продовжити перевірку.

Приклад. Розв’язати рівняння: 2^x  11 (mod 13).

a =  = 4;

L₁: 1, 2⁴  3, 2⁸  9, 2¹²  1, 2¹⁶  3;

L₂: 11, 11 * 2  9, 11 * 2²  5, 11 * 2³  10;

Число 9 зустрілося в обох списках. 11 * 2  2⁸, 11  2⁷, звідки x = 7.

Відповідь: x = 7.

Інший підхід до реалізації алгоритму великого та малого кроку можна отримати якщо рівність b = g^{sa + t} (a = , 0  s, t < a) переписати у вигляді b * (g^-a)^s = g^t. Обчислимо g^-a та складемо таблицю значень g^t, 0  t < a. Далі починаємо знаходити значення b * (g^-a)^s, s = 0, 1, … перевіряючи їх наявність у таблиці g^t. Як тільки знаходяться такі s та t, алгоритм зупиняється.

Приклад. Обчислити log₂3 в групі Z₁₉^* .

3 = 2^x = 2^sa+1, 3 * (2^-a)^s = 2^t. Складемо таблицю 2^t, 0  t <  = 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 * (10⁵)^s (mod 19)  3 * 3^s (mod 19)

Обчислюємо 3 * 3^s, s = 0, 1, … :

s	0	1	2
3 * 3s	3	9	8

Значення 8, яке отримали при s = 2, присутнє в таблиці 2^t, 0  t < 5.

Звідси 3 * (2^-5)² = 2³ або 3 = (2⁵)² * 2³ = 2^5*2+3 = 2¹³.

Відповідь: 3 = 2¹³, тобто log₂3 = 13.

Алгоритм Полард - ро

Нехай G – циклічна група з порядком n (n – просте). Розіб’ємо елементи групи G на три підмножини S₁, S₂ та S₃, які мають приблизно однакову потужність. При цьому необхідне виконання умови: 1 S₂. Визначимо послідовність елементів x_i наступним чином:

x₀ = 1, x_i+1 = , i 0 (1)

Ця послідовність у свою чергу утворить дві послідовності c_i та d_i , що задовольняють умові

x_i =

та визначаються наступним чином:

с₀ = 0, с_i+1 = , i 0 (2)

та

d₀ = 0, d_i+1 = , i 0 (3)

Алгоритм буде працювати циклічно шукаючи таке знчення i, для якого x_i = x_2i. Для таких значень будуть мати місце рівність = або = . Логарифмуючи останню рівність за основою a, матимемо:

(d_i - d_2i) * log_ab (c_2i - c_i) mod n

Якщо d_i  d_2i (mod n), то це рівняння може бути ефективно розв’язано для обчислення log_ab.

Алгоритм

Вхід: генератор a циклічної групи G з порядком n та елемент b G.

Вихід: дискретний логарифм x = log_ab.

1. x₀ 1, c₀ 0, d₀ 0.

2. for i = 1, 2, ... do

2.1. За значеннями x_i-1, c_i-1, d_i-1 та x_2i-2, c_2i-2, d_2i-2 обчислити значення x_i, c_i, d_i та x_2i, c_2i, d_2i використовуючи формули (1), (2), (3).

2.2. if (x_i = x_2i) then

r (d_i - d_2i) mod n;

if (r = 0) then return (FALSE); // розв’язку не знайдено

x  r ^-1 (c_i - c_2i) mod n.

return (x).

Якщо алгоритм завершується невдачею (повертає FALSE), то можна запустити його вибравши інші початкові значення c₀, d₀ з інтервалу [1; n - 1] та поклавши x₀ = .

Приклад. Обчислити log₂9 в групі Z₁₉^*.

Побудуємо наступну таблицю значень послідовностей x_i, c_i, d_i:

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 кроці отримали x₆ = x₁₂ . Підставивши їх значення, отримаємо:

2⁸ * 9⁶ = 2⁶⁴ * 9⁶² або 2^{8 – 64} = 9^{62 – 6} , 2^-56 = 9⁵⁶

Логарифмуємо рівність: -56 * log₂9 = 56 (mod 18), оскільки |Z₁₉^*| = 18.

Враховуючи що -56 (mod 18) 16, 56 (mod 18) 2, перепишемо рівність у вигляді 16 * log₂9 = 2 (mod 18) або 8 * log₂9 = 1 (mod 9). log₂9 = 8^-1 (mod 9) = 8.

Відповідь: log₂9 = 8.

Індексний алгоритм

Алгоритм, базований на обчисленні індексів, є найпотужним при обчисленні дискретного логарифму. Необхідно побудувати відносно невелику підмножину S елементів групи G, яка називається множниковою основою. Ця підмножина повинна обиратися таким чином, щоб як можна більша частина елементів G могла бути представлена у вигляді добутку її елементів. При обчисленні значення log_ab (a – генератор G, b G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b.

Алгоритм

Вхід: генератор a циклічної групи G порядка n та елемент b G.

Вихід: дискретний логарифм x = log_ab.

1. Побудувати множину S – множникову основу. Нехай S = {p₁, p₂, …, p_t}. В якості значень p_i можна обрати, наприклад, i - те просте число.

2. Побудувати систему лінійних рівнянь, розв’язком якої будуть значення log_ap_i. Для цього виконаємо наступні кроки:

2.1. Обрати деяке ціле k, 0 k n - 1 та обчислити a^k .

2.2. Спробувати представити значення a^k у вигляді добутку чисел з S:

a^k = , c_i 0

Якщо така рівність знайдена, то записати рівняння:

k = (mod n)

2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + c лінійних рівнянь. Невелике ціле число c (1  c  10) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку).

3. Розв’язати утворену систему рівнянь, отримати значення log_ap_i, 1 i  t.

4. Обчислення log_ab.

4.1. Обрати деяке ціле k, 0 k n - 1 та обчислити b * a^k .

4.2. Спробувати представити значення b * a^k у вигляді добутку чисел з S:

b * a^k = , d_i 0

Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:

x = log_ab = ( - k) mod n

Приклад. Обчислити log₂12 в групі Z₁₉^*.

1. Нехай S = {2, 3, 5} – множникова основа.

2. Будуємо систему рівнянь для знаходження значень log₂p_i, де p_i S. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.

k = 5: 2⁵ (mod 19)  13 – не представимо у вигляді добутку чисел з S.

k = 7: 2⁷ (mod 19)  14 – не представимо у вигляді добутку чисел з S.

k = 2: 2² (mod 19)  4 = 2². Перше рівняння: 2 = 2log₂2.

k = 10: 2¹⁰ (mod 19)  17 – не представимо у вигляді добутку чисел з S.

k = 15: 2¹⁵ (mod 19)  12 = 2² * 3. Друге рівняння: 15 = 2log₂2 + log₂3.

k = 11: 2¹¹ (mod 19)  15 = 3 * 5. Третє рівняння: 11 = log₂3 + log₂5.

3. Система рівнянь за модулем 18 (порядок Z₁₉^* дорівнює 18) має вигляд:

Її розв’язком буде:

log₂2 = 1, log₂3 = 13, log₂5 = 16

4. Обчислення log₂12.

k = 3: 12 * 2³ (mod 19)  1 – не представимо у вигляді добутку чисел з S.

k = 7: 12 * 2⁷ (mod 19)  16 = 2⁴.

log₂12 + 7  4log₂2 (mod 18), log₂12  (4log₂2 – 7) (mod 18) = 15.

Відповідь: log₂12 = 15.

Алгоритм Поліга – Хелмана

Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники.

Нехай g, h  G, |G| = p^s, p – просте. Тоді значення x = log_gh можна подати у вигляді:

x = x₀ + x₁p + x₂p² + … + x_s-1p^s-1

Піднесемо рівняння h = g^x до степеня p^s-1:

= = =

* * * … * = ,

оскільки = 1 (g – генератор групи, p^s – її порядок).

Таким чином з рівності = знаходимо x₀.

Далі маючи значення x₀, x₁, …, x_i-1 можна обчислити x_i з рівняння

=

Приклад. Обчислити log₃7 в Z₁₇^*.

Необхідно розв’язати рівняння 3^x = 7 в групі, порядок якої дорівнює 16 = 2⁴.

Представимо x у двійковій системі числення: x = x₀ + 2x₁ + 4x₂ + 8x₃.

1. Обчислення x₀.

Піднесемо рівняння 3^x = 7 до степеня 2³ = 8:

= 7⁸, = -1,

* * * = -1.

Оскільки 3¹⁶ (mod 17)  1, то останнє рівняння прийме вигляд = -1. Враховуючи що 3⁸ (mod 17)  -1, маємо: = -1, x₀ = 1.

2. Обчислення x₁.

Домножимо рівність = 7 на = 3^-1 (mod 17) = 6, отримаємо:

= 7 * 6 або = 8.

Піднесемо рівняння до степеня 4: = 8⁴, = -1, x₁ = 1.

3. Обчислення x₂.

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.