WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Дискретний логарифм - Реферат

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


Реферат на тему:
Дискретний логарифм
Проблема обчислення дискретного логарифма є не лише цікавою, а й вкрай корисною для систем захисту інформації. Ефективний алгоритм знаходження дискретного логарифму значною мірою знизив би безпеку систем ідентифікації користувача та схеми обміну ключей.
Означення. Нехай 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* необхідно зробити наступні кроки:
1. Обчислити a = ;
2. Побудувати список L1 = 1, ga, g2a, ..., g (за модулем 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).
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 = gsa + 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, алгоритм зупиняється.
Приклад. Обчислити log23 в групі Z19* .
3 = 2x = 2sa+1, 3 * (2-a)s = 2t. Складемо таблицю 2t, 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 * (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 наступним чином:
x0 = 1, xi+1 = , i 0 (1)
Ця послідовність у свою чергу утворить дві послідовності ci та di , що задовольняють умові
xi =
та визначаються наступним чином:
с0 = 0, сi+1 = , i 0 (2)
та
d0 = 0, di+1 = , i 0 (3)
Алгоритм буде працювати циклічно шукаючи таке знчення i, для якого xi = x2i. Для таких значень будуть мати місце рівність = або = . Логарифмуючи останню рівність за основою 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. За значеннями
Loading...

 
 

Цікаве