Реферат на тему:
Дискретний логарифм
Проблема обчислення дискретного логарифма є не лише цікавою, а й вкрай корисною для систем захисту інформації. Ефективний алгоритм знаходження дискретного логарифму значною мірою знизив би безпеку систем ідентифікації користувача та схеми обміну ключей.
Означення. Нехай G – скінченна циклічна група порядка n. Нехай g – генератор G та b \xF0CE\xF020G. Дискретним логарифмом числа b за основою g називається таке число x (0 \xF0A3\xF020x \xF0A3\xF020n - 1), що gx = b та позначається x = loggb.
Проблема дискретного логарифму. Нехай p – просте число, g – генератор множини Zp*, y \xF0CE Zp*. Знайти таке значення x (0 \xF0A3 x \xF0A3 p - 2), що gx \xF0BA y (mod p). Число x називається дискретним логарифмом числа y за основою g та модулем p.
Узагальнена проблема дискретного логарифму. Нехай G – скінченна циклічна група порядка n, g – її генератор, b \xF0CE\xF020G. Необхідно знайти таке число x (0 \xF0A3\xF020x \xF0A3\xF020n - 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 \xF0CE 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 \xF0CE\xF020G) будемо обчислювати значення g, g2, g3, g4, ... поки не отримаємо b. Часова оцінка алгоритму – O(n). Якщо n – велике число, то час обчислення логарифму є достатньо великим і тому алгоритм є неефективним.
Алгоритм великого та малого кроку
Першим детермінованим алгоритмом для обчислення дискретного логарифму був алгоритм великого та малого кроку, запропонований Шанком (Shank) [1].
Для обчислення loggb в групі Zn* необхідно зробити наступні кроки:
\xF020\xF0F9\xF020;
(за модулем 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 \xF0A3 s, t < a. Тоді b = gx = gsa + t. Домножимо рівність на ga - t, отримаємо: bga - t = gs(a + 1). Значення зліва обов’язково зустрінеться в L2, а справа – в L1.
Відсортуємо отримані списки L1 та L2 за час O(a * log a). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z знайдене, якщо ні – то видалити менше число і продовжити перевірку.
|
Скачати "Реферат на тему Дискретний логарифм"
