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

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

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

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

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

Проблема дискретного логарифму. Нехай p – просте число, g – генератор множини Z_p ^* , y ÎZ_p ^* . Знайти таке значення x (0 £x £p - 2), що g^x ºy (modp ). Число 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_a k , y = log_b k , z = log_a b . Тоді a ^x = b ^y = (a ^z )^y , звідки x = zymodn. Підставимо в останню рівність замість змінних логарифмічні вирази:

log_a k =(log_a b) (log_b k) modn

або

log_b k =(log_a k) (log_a b)^-1 modn.

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

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

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

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

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

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

1. Обчислити a = é ù ;

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

Відсортуємо отримані списки L₁ та L₂ за час O(a * loga ). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення 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^{s a + 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:

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, … :

Значення 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 _{2 i} . Для таких значень будуть мати місце рівність = або = . Логарифмуючи останню рівність за основою a , матимемо:

(d _i - d _2i ) * log_a b º (c _2i - c _i ) mod n

Якщо d _i ¹d _{2 i} (modn), то це рівняння може бути ефективно розв’язано для обчислення log_a b .

Алгоритм

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

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

1. x₀ ¬ 1, c ₀ ¬ 0, d ₀ ¬ 0.

2. fori = 1, 2, ... do

2.1. За значеннями x_{i -1} , c_{i -1} , d_{i -1} та x _{2 i -2} , c _{2 i -2} , d _{2 i -2} обчислити значення x_i , c_i , d_i та x _{2 i} , c _{2 i} , d _{2 i} використовуючи формули (1), (2), (3).

2.2. if (x _i = x _{2 i} ) then

r ¬ (d_i - d _{2 i} ) modn ;

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

x ¬r ^-1 (c_i - c _{2 i} ) mod n .

return (x ).

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

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

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

На 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_a b (a – генератор G, b Î G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b .

Алгоритм

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

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

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

2. Побудувати систему лінійних рівнянь, розв’язком якої будуть значення log_a p_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_a p_i , 1£i £t .

4. Обчислення log_a b .

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_a b = ( - 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_g h можна подати у вигляді:

x = x ₀ + x ₁ p + x ₂ p ² + … + x_{s -1} p^{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.