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

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

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

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

Проблема дискретного логарифму. Нехай p — просте число, g — генератор множини Zp*, y *. Знайти таке значення x (0 — 2), що gx (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 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 = ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >n /div>

2. Побудувати список L1 = 1, ga, g2a, …, g $${}^{a^2}$$ (за модулем n);

3. Побудувати список L2 = b, bg, bg2, …, bga — 1 (за модулем n);

4. Знайти число z, яке зустрілося в L1 та L2.

Тоді z = bgk = gla для деяких k та l. Звідси b = gla — k = gxx = la — k.

Два питання постає при дослідженні роботи наведеного алгоритму:

1. Чи завжди знайдеться число, яке буде присутнім в обох списках?

2. Як ефективно знайти значення z?

Запишемо x = sa + t для деяких s, t таких що 0 t < a. Тоді b = gx = gsa + t. Домножимо рівність на ga — t, отримаємо: bga — t = gs (a + 1). Значення зліва обов’язково зустрінеться в L2, а справа — в L1.

Відсортуємо отримані списки L1 та L2 за час O (a * log a). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z знайдене, якщо ні - то видалити менше число і продовжити перевірку.

Приклад. Розв’язати рівняння: 2x (mod 13).

a = ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >13 = 4;

L1: 1, 24 28 212 216.

L2: 11, 11 * 2 11 * 22 11 * 23 ;

Число 9 зустрілося в обох списках. 11 * 2, 11, звідки x = 7.

Відповідь: x = 7.

Інший підхід до реалізації алгоритму великого та малого кроку можна отримати якщо рівність b = gsa + t (a = ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >n t < a) переписати у вигляді b * (g-a)s = gt. Обчислимо g-a та складемо таблицю значень gt, 0 < a. Далі починаємо знаходити значення b * (g-a)s, s = 0, 1, … перевіряючи їх наявність у таблиці gt. Як тільки знаходяться такі s та t, алгоритм зупиняється.

Приклад. Обчислити log23 в групі Z19* .

3 = 2x = 2sa+1, 3 * (2-a)s = 2t. Складемо таблицю 2t, 0 < ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >19 = 5:

t.
2t.

2−1 (mod 19), оскільки 2 * 10 (mod 19).

Тоді 3 * (2−5)s (mod 19) * (105)s (mod 19) * 3s (mod 19).

Обчислюємо 3 * 3s, s = 0, 1, … :

s.
3 * 3s.

Значення 8, яке отримали при s = 2, присутнє в таблиці 2t, 0 < 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 = $$\begin{array}{c}b{x}_i,x_i{S}_1\\ x_i^2,x_i{S}_2\\ a{x}_i,x_i{S}_3\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$, i 0 (1).

Ця послідовність у свою чергу утворить дві послідовності ci та di, що задовольняють умові.

xi = $$a^{c_i}{b}^{d_i}$$.

та визначаються наступним чином:

с0 = 0, сi+1 = $$\begin{array}{c}{c}_i,x_i{S}_1\\ (2c_i)\text{mod}n,x_i{S}_2\\ (c_i+1)\text{mod}n,x_i{S}_3\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$, i 0 (2).

та.

d0 = 0, di+1 = $$\begin{array}{c}(d_i+1)\text{mod}n,x_i{S}_1\\ (2d_i)\text{mod}n,x_i{S}_2\\ d_i,x_i{S}_3\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$, i 0 (3).

Алгоритм буде працювати циклічно шукаючи таке знчення i, для якого xi = x2i. Для таких значень будуть мати місце рівність $$a^{c_i}{b}^{d_i}$$ = $$a^{c_{2i}}{b}^{d_{2i}}$$ або $$b^{d_i-d_{2i}}$$ = $$a^{c_{2i}-c_i}$$. Логарифмуючи останню рівність за основою a, матимемо:

(di — d2i) * logab (c2i — ci) mod n.

Якщо di i (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. За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).

2.2. if (xi = x2i) then.

r (di — d2i) mod n;

if (r = 0) then return (FALSE) — // розв’язку не знайдено.

x -1 (ci — c2i) mod n.

return (x).

Якщо алгоритм завершується невдачею (повертає FALSE), то можна запустити його вибравши інші початкові значення c0, d0 з інтервалу [1- n — 1] та поклавши x0 = $$a^{c_0}{b}^{d_0}$$ .

Приклад. Обчислити log29 в групі Z19*.

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

i.	xi.	ai.	bi.	x2i.	a2i.	b2i.

На 6 кроці отримали x6 = x12. Підставивши їх значення, отримаємо:

28 * 96 = 264 * 962 або 28 — 64 = 962 — 6, 2−56 = 956.

Логарифмуємо рівність: -56 * log29 = 56 (mod 18), оскільки |Z19*| = 18.

Враховуючи що -56 (mod 18) 16, 56 (mod 18) 2, перепишемо рівність у вигляді 16 * log29 = 2 (mod 18) або 8 * log29 = 1 (mod 9). log29 = 8−1 (mod 9) = 8.

Відповідь: log29 = 8.

Індексний алгоритм

Алгоритм, базований на обчисленні індексів, є найпотужним при обчисленні дискретного логарифму. Необхідно побудувати відносно невелику підмножину S елементів групи G, яка називається множниковою основою. Ця підмножина повинна обиратися таким чином, щоб як можна більша частина елементів G могла бути представлена у вигляді добутку її елементів. При обчисленні значення logab (a — генератор G, b G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b.

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

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

1. Побудувати множину S — множникову основу. Нехай S = {p1, p2, …, pt}. В якості значень pi можна обрати, наприклад, i — те просте число.

2. Побудувати систему лінійних рівнянь, розв’язком якої будуть значення logapi. Для цього виконаємо наступні кроки:

2.1. Обрати деяке ціле k, 0 k n — 1 та обчислити ak .

2.2. Спробувати представити значення ak у вигляді добутку чисел з S:

ak = $$\underset{i=1}{\overset{t}{}}{p}_i^{c_i}$$, ci 0.

Якщо така рівність знайдена, то записати рівняння:

k = $$\underset{i=1}{\overset{t}{}}{c}_i{\text{log}}_a{p}_i$$ (mod n).

2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + c лінійних рівнянь. Невелике ціле число c (1) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку).

3. Розв’язати утворену систему рівнянь, отримати значення logapi, 1.

4. Обчислення logab.

4.1. Обрати деяке ціле k, 0 k n — 1 та обчислити b * ak .

4.2. Спробувати представити значення b * ak у вигляді добутку чисел з S:

b * ak = $$\underset{i=1}{\overset{t}{}}{p}_i^{d_i}$$, di 0.

Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:

x = logab = ($$\underset{i=1}{\overset{t}{}}{d}_i{\text{log}}_a{p}_i$$ — k) mod n.

Приклад. Обчислити log212 в групі Z19*.

1. Нехай S = {2, 3, 5} - множникова основа.

2. Будуємо систему рівнянь для знаходження значень log2pi, де pi S. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.

k = 5: 25 (mod 19) — не представимо у вигляді добутку чисел з S.

k = 7: 27 (mod 19) — не представимо у вигляді добутку чисел з S.

k = 2: 22 (mod 19) = 22. Перше рівняння: 2 = 2log22.

k = 10: 210 (mod 19) — не представимо у вигляді добутку чисел з S.

k = 15: 215 (mod 19) = 22 * 3. Друге рівняння: 15 = 2log22 + log23.

k = 11: 211 (mod 19) = 3 * 5. Третє рівняння: 11 = log23 + log25.

3. Система рівнянь за модулем 18 (порядок Z19* дорівнює 18) має вигляд:

$$\begin{array}{c}2=2{\text{log}}_{2}2(\text{mod 18})\\ \text{15}=2{\text{log}}_{2}2+{\text{log}}_{2}3(\text{mod}\text{18})\\ \text{11}={\text{log}}_{2}3+{\text{log}}_{2}5(\text{mod 18})\\ \\ \begin{array}{c}\{\{\end{array}\hfill \\ \end{array}$$.

Її розв’язком буде:

log22 = 1, log23 = 13, log25 = 16.

4. Обчислення log212.

k = 3: 12 * 23 (mod 19) — не представимо у вигляді добутку чисел з S.

k = 7: 12 * 27 (mod 19) = 24.

log212 + 7 og22 (mod 18), log212 log22 — 7) (mod 18) = 15.

Відповідь: log212 = 15.

Алгоритм Поліга — Хелмана Алгоритм Поліга — Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники.

Нехай g, h |G| = ps, p — просте. Тоді значення x = loggh можна подати у вигляді:

x = x0 + x1p + x2p2 + … + xs-1ps-1.

Піднесемо рівняння h = gx до степеня ps-1:

$$h^{p^{s-1}}$$ = $${\left(g^{p^{s-1}}\right)}^x$$ = $${\left(g^{p^{s-1}}\right)}^{x_0+x_{1}p+x_2{p}^2+\text{.}\text{.}\text{.}+x_{s-1}{p}^{s-1}}$$ =.

$${\left(g^{p^{s-1}}\right)}^{x_0}$$ * $${\left(g^{p^s}\right)}^{x_1}$$ * $${\left(g^{p^s}\right)}^{{\text{px}}_2}$$ * … * $${\left(g^{p^s}\right)}^{p^{\text{s-}2}{x}_{\text{s-}1}}$$ = $${\left(g^{p^{s-1}}\right)}^{x_0}$$ ,.

оскільки $$g^{p^s}$$ = 1 (g — генератор групи, ps — її порядок).

Таким чином з рівності $$h^{p^{s-1}}$$ = $${\left(g^{p^{s-1}}\right)}^{x_0}$$ знаходимо x0.

Далі маючи значення x0, x1, …, xi-1 можна обчислити xi з рівняння.

$${\left(h{g}^{-\underset{j=0}{\overset{i-1}{}}{x}_j{p}^j}\right)}^{p^{s-(i+1)}}$$ = $${\left(g^{p^{s-1}}\right)}^{x_i}$$.

Приклад. Обчислити log37 в Z17*.

Необхідно розв’язати рівняння 3x = 7 в групі, порядок якої дорівнює 16 = 24.

Представимо x у двійковій системі числення: x = x0 + 2×1 + 4×2 + 8×3.

1. Обчислення x0.

Піднесемо рівняння 3x = 7 до степеня 23 = 8:

$$3^{8(x_0+2x_1+4x_2+8_3)}$$ = 78, $$3^{8x_0+\text{16}{x}_1+\text{32}{x}_2+{\text{64}}_3}$$ = -1,.

$$3^{8x_0}$$ * $$(3^{\text{16}}{)}^{x_1}$$ * $$(3^{\text{16}}{)}^{2x_2}$$ * $$(3^{\text{16}}{)}^{4x_3}$$ = -1.

Оскільки 316 (mod 17) то останнє рівняння прийме вигляд $$3^{8x_0}$$ = -1. Враховуючи що 38 (mod 17), маємо: $$(-1{)}^{x_0}$$ = -1, x0 = 1.

2. Обчислення x1.

Домножимо рівність $$3^{x_0+2x_1+4x_2+8_3}$$ = 7 на $$3^{-x_0}$$ = 3−1 (mod 17) = 6, отримаємо:

$$3^{2x_1+4x_2+8_3}$$ = 7 * 6 або $$3^{2x_1+4x_2+8_3}$$ = 8.

Піднесемо рівняння до степеня 4: $$3^{8x_1+\text{16}{x}_2+{\text{32}}_3}$$ = 84, $$3^{8x_1}$$ = -1, x1 = 1.

3. Обчислення x2.

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.

.