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.


 

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

23095. Fast Ethernet и 100VG-AnyLAN как развитие технологии Ethernet 151 KB
  В результате поисков и исследований специалисты разделились на два лагеря, что в конце концов привело к появлению двух новых технологий — Fast Ethernet и 100VG-AnyLAN. Они отличаются степенью преемственности с классическим Ethernet.
23096. Розсіяння електромагнітних хвиль зарядами. Формула Томсона 76.5 KB
  Розсіяння електромагнітних хвиль зарядами. Цей рух в свою чергу супроводжується випромінюванням в усі боки: відбувається розсіяння початкової хвилі. Нехай енергія яка випромінюється системою в тілесний кут в 1с при тому що на неї падає хвиля з вектором Пойнтінга Тоді переріз розсіяння риска означає усереднення по часу Розглянемо розсіяння що проводиться одним нерухомим зарядом вільним зарядом. отримана зарядом швидкість припускається малою 2 1 в 2: одиничний вектор в напрямку розсіяння.
23097. Квантування електромагнітного поля. Фотони 87 KB
  Квантування електромагнітного поля. Ейнштейн першим звернув на це увагу і намагався теоретично обґрунтувати дискретність електромагнітного випромінювання. Ейнштейн показав що ймовірність мати енергію для електромагнітного випромінювання буде: . Для електромагнітного випромінювання: .
23098. Поширення світла в анізотропних середовищах. Дисперсія і поглинання 466 KB
  В анізотропному середовищі спостерігається подвійне заломлення променів зумовлене наявністю в них двох показників заломлення один з яких не залежить від напрямку поширення хвилі і відповідає одній поляризації а другий залежить від напрямку поширення і пов`язаний з іншою поляризацією. Введемо для ізотропного середовища показник заломлення. Для хвилі що поширюється в напрямку – x коливання відбуваються в напрямку z то показник заломлення більше в напрямку z ніж для коливань в напрямку – y. z – напрямок при якому показники...
23099. Явище обертання площини поляризації падаючого світла в речовинах 96 KB
  Явище обертання площини поляризації падаючого світла в речовинах. Якщо лінійно поляризоване світло проходить через плоскопаралельний шар речовини то в деяких випадках площина поляризації світла виявляється повернутою відносно свого вихідного положення. Це явище називається обертанням площини поляризації або оптичною активністю. Кут поворота площини поляризації залежить від довжини хвилі.
23100. Квантування енергії лінійного гармонічного осцилятора 202.5 KB
  Тоді гамільтоніан для такої системи буде: Класичний гармонічний осцилятор має розв’язки: і де А амплітуда ω – частота δ – початкова фаза коливань. Перетворимо це рівняння введемо безрозмірні величини та З урахуванням останнього рівняння Шредігера перепишеться як 1 Асимптотична поведінка розв’язку рівняння 1 при х→∞: Тоді 2 причому uzобмежена на нескінченності. Шукаючи розв’язок у вигляді степеневого ряду знаходимо рекурентну формулу для коефіцієнтів ряду: Розв’язки можуть бути або парними або непарними тобто або...
23101. Хвильові властивості частинок. Хвилі де Бройля 5.02 MB
  Хвилі де Бройля. Тобто інколи відбувається прояв як хвилі інколи як частинки. Тоді можна отримати вираз для хвилі де Бройля . Оберемо напрям вздовж за напрям розповсюдження хвилі де фаза хвилі що пересувається у просторі з фазовою швидкістю що шукається з умови що переміщується так щоб фаза залишалась постійною .
23102. Принципова схема лазера. Властивості лазерного випромінювання. Типи лазерів та їх застосування 51.5 KB
  При падінні хвилі з власною частотою переходу системи: змінюються заселеності рівнів N1 i N2 кількість атомів в одиниці об’єму що знаходяться на 1 та на 2 енергетичних рівнях відповідно. dN12=BN1dt ; кількість частинок що перейшли з 1 рівня на 2 dN21= AN2dt BN2dt кількість частинок що перейшли з 2 рівня на 1 де Акоеф. Крім того в стаціонарному режимі при умові термодинамічної рівноваги виконуються рівняння: N1N2=N=const кількість частинок в системі є сталою. В дворівневій системі не можна забезпечити умову N2 N1 бо навіть в...
23103. Рівняння Шредингера. Інтерпретація хвильової функції 49 KB
  Рівняння Шредингера. Для цього необхідне рівняння: 1. Рівняння повинно бути лінійним і однорідним хвиля задовольняє принц. Це рівняння Шредингера.