Реферат на тему:
Дискретний логарифм
Проблема обчислення дискретного логарифма є не лише цікавою, а й вкрай корисною для систем захисту інформації. Ефективний алгоритм знаходження дискретного логарифму значною мірою знизив би безпеку систем ідентифікації користувача та схеми обміну ключей.
Означення
. Нехай 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.
З останньої рівності випливає справедливість теореми.
Примітивний алгоритм
Для знаходження logg
b
(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
2
a
, ..., 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 | 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
, тобто 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
2
i
. Для таких значень будуть мати місце рівність = або = . Логарифмуючи останню рівність за основою a
, матимемо:
(d
i
- d
2i
) * loga
b
º (c
2i
- c
i
) mod n
Якщо d
i
¹d
2
i
(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
2
i
-2
, c
i
-2
, d
2
i
-2
обчислити значення xi
, ci
, di
та x
2
i
, c
2
i
, d
2
i
використовуючи формули (1), (2), (3).
2.2. if (x
i
= x
2
i
) then
r
¬ (di
- d
2
i
) modn
;
if (r
= 0) thenreturn (FALSE); // розв’язку не знайдено
x
¬r
-1
(ci
- c
2
i
) 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
2 i |
| 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 кроці отримали 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. Будуємо систему рівнянь для знаходження значень log2
pi
, де 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
1
p
+ x
2
p
2
+ … + xs
-1
ps
-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.