Реферат: Дискретний логарифм
Реферат на тему:
Дискретний логарифм
Проблема обчислення дискретного логарифма є не лише цікавою, а й вкрай корисною для систем захисту інформації. Ефективний алгоритм знаходження дискретного логарифму значною мірою знизив би безпеку систем ідентифікації користувача та схеми обміну ключей.
Означення. Нехай G – скінченна циклічна група порядка n. Нехай g – генератор G та b Î G. Дискретним логарифмом числа b за основою g називається таке число x (0 £ x £ n — 1), що gx = b та позначається x = logg b .
Проблема дискретного логарифму. Нехай p – просте число, g – генератор множини Zp *, y ÎZp *. Знайти таке значення x (0 £x £p — 2), що gx ºy (modp ). Число x називається дискретним логарифмом числа yза основою g та модулем p .
Узагальнена проблема дискретного логарифму. Нехай G – скінченна циклічна група порядка n, g – її генератор, b Î G. Необхідно знайти таке число x (0 £ x £ n — 1), що gx = b .
Розширенням узагальненої проблеми може стати задача розв’язку рівняння g x = b, коли знято умову циклічності групиG, а також умову того, що g – генератор G (в такому випадку рівняння може і не мати розв’язку).
Приклад. g = 3 є генератором Z7 *: 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1.
log3 4 = 4 (mod 7), тому що розв’язком рівняння 3x = 4 буде x = 4.
Теорема. Нехай а – генератор скінченної циклічної групи G порядка n. Якщо існує алгоритм, який обчислює дискретний логарифм за основою а, то цей алгоритм може також обчислити дискретний логарифм за будь-якою основою b, яка є генератором G.
Доведення. Нехай k ÎG, x = loga k, y = logb k, z = loga b. Тоді a x = b y = (a z )y, звідки x = zymodn. Підставимо в останню рівність замість змінних логарифмічні вирази:
loga k =(loga b) (logb k) modn
або
logb k =(loga k) (loga b)-1 modn.
З останньої рівності випливає справедливість теореми.
Примітивний алгоритм
Для знаходження loggb (g – генератор G порядка n, b Î G) будемо обчислювати значення g, g 2, g 3, g 4,… поки не отримаємо b. Часова оцінка алгоритму – O(n ). Якщо n – велике число, то час обчислення логарифму є достатньо великим і тому алгоритм є неефективним.
Алгоритм великого та малого кроку
Першим детермінованим алгоритмом для обчислення дискретного логарифму був алгоритм великого та малого кроку, запропонований Шанком (Shank) [1].
Для обчислення logg b в групі Zn * необхідно зробити наступні кроки:
1. Обчислити a = é ù ;
2. Побудувати списокL1 = 1, g a, g 2a, ..., g (за модулем n );
3. Побудувати списокL2 = b, bg, bg 2, ..., bg a — 1 (за модулем n );
4. Знайти число z, яке зустрілося в L1 та L2.
Тоді z = bgk = g la для деяких k та l. Звідси b = gla — k = gx; x = la — k .
Два питання постає при дослідженні роботи наведеного алгоритму:
1. Чи завжди знайдеться число, яке буде присутнім в обох списках?
2. Як ефективно знайти значення z?
Запишемо x = s a + t для деяких s, t таких що 0 £s, t < a. Тоді b = gx = gs a + t. Домножимо рівність на g a — t, отримаємо: bg a — t = gs (a + 1). Значення зліва обов’язково зустрінеться в L2, а справа – в L1 .
Відсортуємо отримані списки L1 та L2 за час O(a * loga ). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z знайдене, якщо ні – то видалити менше число і продовжити перевірку.
Приклад. Розв’язати рівняння: 2x º 11 (mod 13).
a = é ù = 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.
Інший підхід до реалізації алгоритму великого та малого кроку можна отримати якщо рівність b = gs a + t (a = é ù, 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, алгоритм зупиняється.
Приклад. Обчислити log2 3 в групі Z19* .
3 = 2x = 2sa +1, 3 * (2-a )s = 2t. Складемо таблицю 2t, 0£t < é ù = 5:
t | 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 | 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, тобто log2 3 = 13.
Алгоритм Полард — ро
Нехай G – циклічна група з порядком n (n – просте). Розіб’ємо елементи групи G на три підмножини S1, S2 та S3, які мають приблизно однакову потужність. При цьому необхідне виконання умови: 1 Ï S2. Визначимо послідовність елементів x i наступним чином:
x 0= 1, x i+1 =, i ³ 0 (1)
Ця послідовність у свою чергу утворить дві послідовності c i та d i, що задовольняють умові
x i =
та визначаються наступним чином:
с 0= 0, с i+1 =, i³ 0 (2)
та
d 0= 0, d i+1 =, i ³ 0 (3)
Алгоритм буде працювати циклічно шукаючи таке знчення i, для якого x i = x 2i. Для таких значень будуть мати місце рівність = або =. Логарифмуючи останню рівність за основою a, матимемо:
(d i — d 2i ) * loga b º (c 2i — c i ) modn
Якщо d i ¹d 2i (modn), то це рівняння може бути ефективно розв’язано для обчислення loga b .
Алгоритм
Вхід: генератор a циклічної групи G з порядком nта елемент b Î G.
Вихід: дискретний логарифм x = loga b .
1. x0¬ 1, c 0¬ 0, d 0¬ 0.
2. fori = 1, 2,… do
2.1. За значеннями xi -1, ci -1, di -1 та x 2i -2, c 2i -2, d 2i -2 обчислити значення xi, ci, di та x 2i, c 2i, d 2i використовуючи формули (1), (2), (3).
2.2. if (x i = x 2i ) then
r ¬ (di — d 2i ) modn ;
if (r = 0) thenreturn (FALSE); // розв’язку не знайдено
x ¬r -1 (ci — c 2i ) mod n .
return (x ).
Якщо алгоритм завершується невдачею (повертає FALSE), то можна запустити його вибравши інші початкові значення c 0, d 0з інтервалу [1; n — 1] та поклавши x0= .
Приклад. Обчислити log2 9в групі Z19* .
Побудуємо наступну таблицю значень послідовностей xi, ci, di :
i | xi | ai | bi | x 2i | a 2i | b 2i |
1 | 9 | 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 * log2 9 = 56 (mod 18), оскільки |Z19* | = 18.
Враховуючи що -56 (mod 18) º 16, 56 (mod 18) º 2, перепишемо рівність у вигляді 16 * log2 9 = 2 (mod 18) або 8 * log2 9 = 1 (mod 9). log2 9 = 8-1 (mod 9) = 8.
Відповідь: log2 9 = 8.
Індексний алгоритм
Алгоритм, базований на обчисленні індексів, є найпотужним при обчисленні дискретного логарифму. Необхідно побудувати відносно невелику підмножину S елементів групи G, яка називається множниковою основою . Ця підмножина повинна обиратися таким чином, щоб як можна більша частина елементів G могла бути представлена у вигляді добутку її елементів. При обчисленні значення loga b (a – генератор G, b Î G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b .
Алгоритм
Вхід: генератор a циклічної групи G порядка n та елемент b Î G.
Вихід: дискретний логарифм x = loga b .
1. Побудувати множину S – множникову основу. Нехай S = {p 1, p 2, …, pt }. В якості значень pi можна обрати, наприклад, i — те просте число.
2. Побудувати систему лінійних рівнянь, розв’язком якої будуть значення loga pi. Для цього виконаємо наступні кроки:
2.1. Обрати деяке ціле k, 0 £ k £ n — 1 та обчислити ak .
2.2. Спробувати представити значення ak у вигляді добутку чисел з S:
ak =, ci ³ 0
Якщо така рівність знайдена, то записати рівняння:
k = (mod n )
2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + c лінійних рівнянь. Невелике ціле число c (1 £c £ 10) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку).
3. Розв’язати утворену систему рівнянь, отримати значення loga pi, 1£i £t .
4. Обчислення loga b .
4.1. Обрати деяке ціле k, 0 £ k £ n — 1 та обчислити b *ak .
4.2. Спробувати представити значення b *ak у вигляді добутку чисел з S:
b *a k =, di ³ 0
Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:
x = loga b = ( — k ) mod n
Приклад. Обчислити log2 12 в групі 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 = 2log2 2.
k = 10: 210 (mod 19) º17 – не представимо у вигляді добутку чисел з S.
k = 15: 215 (mod 19) º12 = 22 * 3. Друге рівняння: 15 = 2log2 2 + log2 3.
k = 11: 211 (mod 19) º15 = 3 * 5. Третє рівняння: 11 = log2 3 + log2 5.
3. Система рівнянь за модулем 18 (порядок Z19* дорівнює 18) має вигляд:
Її розв’язком буде:
log2 2 = 1, log2 3 = 13, log2 5 = 16
4. Обчислення log2 12.
k = 3: 12 * 23 (mod 19) º 1 – не представимо у вигляді добутку чисел з S.
k = 7: 12 * 27 (mod 19) º16 = 24 .
log2 12 + 7 º 4log2 2 (mod 18), log2 12 º (4log2 2 – 7) (mod 18) = 15.
Відповідь: log2 12 = 15.
Алгоритм Поліга – Хелмана
Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники.
Нехай g, h ÎG, |G| = ps, p – просте. Тоді значення x = logg h можна подати у вигляді:
x = x 0+ x 1p + x 2p 2 + … + xs -1ps -1
Піднесемо рівняння h = gx до степеняps -1 :
= = =
* * * … * = ,
оскільки = 1 (g – генератор групи, ps – її порядок).
Таким чином з рівності = знаходимо x 0.
Далі маючи значення x 0, x 1, …, xi -1 можна обчислити xi з рівняння
=
Приклад. Обчислити log3 7 в Z17* .
Необхідно розв’язати рівняння 3x = 7 в групі, порядок якої дорівнює 16 = 24 .
Представимо x у двійковій системі числення: x = x 0+ 2x 1 + 4x 2 + 8x 3 .
1. Обчислення x 0.
Піднесемо рівняння 3x = 7 до степеня 23 = 8:
= 78, = -1,
* * * = -1.
Оскільки 316 (mod 17) º 1, тоостаннє рівняння прийме вигляд = -1. Враховуючи що 38 (mod 17) º -1, маємо: = -1, x 0= 1.
2. Обчислення x 1 .
Домножимо рівність = 7 на = 3-1 (mod 17) = 6, отримаємо:
= 7 * 6 або = 8.
Піднесемо рівняння до степеня 4: = 84, = -1, x1 = 1.
3. Обчислення x 2 .
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.