3941

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

Доклад

Математика и математический анализ

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

Украинкский

2012-11-10

103.5 KB

1 чел.

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

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

Означення. Нехай 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. За значеннями 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 ¬ r -1 (ci - c2i) mod n.

return (x).

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

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

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

i

xi

ai

bi

x2i

a2i

b2i

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 * 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 = , ci ³ 0

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

k =  (mod n)

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

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

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

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

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

b * ak = , di ³ 0

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

x = logab = ( - k) mod n

Приклад. Обчислити log212 в групі 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 = 2log22.

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

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

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

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

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

log22 = 1, log23 = 13, log25 = 16

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

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

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

log212 + 7 º 4log22 (mod 18), log212 º (4log22 – 7) (mod 18) = 15.

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

Алгоритм Поліга – Хелмана

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

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

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

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

=  =  =

*  *  * … *  = ,

оскільки  = 1 (g – генератор групи,  ps – її порядок).

Таким чином з рівності  =  знаходимо x0.

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

=

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

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

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

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

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

= 78,  = -1,

*  *  *  = -1.

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

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

Домножимо рівність  = 7 на  = 3-1 (mod 17) = 6, отримаємо:

= 7 * 6 або  = 8.

Піднесемо рівняння до степеня 4:  = 84,  = -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.


 

А также другие работы, которые могут Вас заинтересовать

4681. Мотивація, контроль та оцінка діяльності педагогів в шкільному менеджменті 605 KB
  Мотивація, контроль та оцінка діяльності педагогів у шкільному менеджменті Одним із важливих психологічних елементів управлінського процесу є мотивація, тобто спонукання керівником себе та інших до досягнення особистих цілей і цілей організації...
4682. Етика та етичні категорії 831.5 KB
  Походження і зміст термінів етика, мораль, моральність 1. Походження термінів 2. Зміст термінів 1. Термін етика походить від давньогрецького слова етос - дім, гніздо. Пізніше воно стало означати характер явища, його природу. Ари...
4683. Історія становлення філософії науки 38.05 KB
  Історія становлення філософії науки. Філософія і наука − два раціональні теоретичні способи освоєння дійсності. І це їх об’єднує. Однак форми освоєння дійсності у філософії та науці різні...
4684. Філософія та релігія. Курс лекцій 882.5 KB
  Філософія та релігія Розкриває зміст світоглядної проблематики та специфіку філософського і релігійного підходів до неї, становлення та основні етапи розвитку філософії у зв’язку з розвитком релігії в країнах європейської культури, особливості ...
4685. Філософія. Світоглядні та філософські істини. Конспект лекцй 897.5 KB
  Тема І. Предмет філософії та її формування План Філософія та світогляд. Історичні типи світогляду. Структурні елементи системи філософського знання. Філософські ідеї Давнього Сходу. Філософія Давньої Греції. Питання...
4686. Місцеві фінанси 54 KB
  Місцеві фінанси Суть місцевих фінансів, їх роль в економічному і соціальному розвитку територій. Місцеві бюджети, їх зміст і роль. Доходи і видатки місцевих бюджетів. Регіональні позабюджетні фонди. 1. Суть місцевих фінансів, їх роль у економі...
4687. Державні цільові фонди 54.5 KB
  Державні цільові фонди Необхідність державних цільових фондів та правові основи їх утворення. Пенсійний фонд України, його функції, формування та використання. Фонд соціального страхування України, його функції, формування та викор...
4688. Загальна фізика. Механіка, молекулярна фізика і термодинаміка, електрика 3.84 MB
  Вступ Фізика є основною наукою про природу. Вона вивчає найбільш загальні властивості і форми руху матерії. Одним із видів руху є механічний рух, під яким розуміють зміну положення тіла в просторі з часом. Механіка Галілея-Ньютона вивчає рух макроск...
4689. Физиология микроорганизмов. Химический состав микробов 530 KB
  Физиология микроорганизмов Микроорганизмам, как и всем живым существам, присущи процессы питания, дыхания, роста и размножения. Однако эти процессы у микробов характеризуются своеобразием и рядом особенностей. Микробы занимают особое место среди дру...