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.


 

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

24686. Управлінський облік. Предмет управлінського обліку 26.5 KB
  управлінського персонала різного рівня для плануванняоцінки та контролю всередині підприємства Предметом управлінського обліку виступає сукупність об’єктів в процесі всього циклу управління підприємством.Об’єктами обліку виступають виробничі ресурси запаси обладнання трудові ресурси та господарські процеси.Методом управлінського обліку виступає сукупність різних прийомів і способів за допомогою яких відображаються об’єкти управлінського обліку в інформаційній системі підприємства. КонтрольМетою управлінського обліку є оптимізація витрат...
24687. Організація обліку за центрами відповідальності 42.5 KB
  Центри відповідальності організуються шляхом делегування відповідним підрозділом підприємства певних повноважень і відповідальності. Основними принципами організації системи обліку за центрами відповідальності є: визначення контрольованих статей витрат і доходів за умови що менеджер керівник повинен відповідати тільки за ті витрати і доходи які він може контролювати і на величину яких може впливати; персоніфікація облікових документів тобто зазначення в документах керівника який відповідає за конкретні статті витрат і доходів; ...
24688. Користувачі інформації 24 KB
  Внутрішні – керівники різних рівнів управліннязабезпечується інформацією на всіх рівнях управління для прийняття поточних рішень 2. Зовнішні акціонерикредиторипостачальникипокупціінвесториподаткові і державні организабезпечується інформацієюяка характеризує результати яких досягло підприємство за минулі звітні роки.
24690. Класифікація витрат 37 KB
  За центрами відповідальності місцем виникнення Витрати виробництва цеху дільниці технологічного переділу служби. За видами продукції Витрати на вироби типові представники виробів групи однорідних виробів одноразові замовлення напівфабрикати. За єдністю складу витрат Одноелементні витрати і комплексні витрати. Наприклад: одноелементні – сировина матеріали прямі витрати на оплату праці; комплексні витрати – їх облік ведуть окремо за елементами та статтями: 919293 4.
24691. ПРИНЦИП ДЕЙСТВИЯ ПРОДОЛЬНОЙ ДИФФЕРЕНЦИАЛЬНОЙ ЗАЩИТЫ 122 KB
  Принцип действия продольных дифференциальных РЗ основан на сравнении значения и фазы токов в начале и конце защищаемой ЛЭП.1 а при внешнем КЗ в точке К токи I1 и I11 на концах ЛЭП АВ направлены в одну сторону и равны по значению а при КЗ на защищаемой ЛЭП рис. Следовательно сопоставляя значение и фазу токов I1 и I11 можно определять где возникло КЗ на защищаемой ЛЭП или за ее пределами.
24692. ЗАЩИТA ГЕНЕРАТОРОВ 41.5 KB
  Подобная защита начала также применяться и в отечественной практике. ЗАЩИТА ОТ МЕЖДУФАЗНЫХ КОРОТКИХ ЗАМЫКАНИЙ В ОБМОТКЕ СТАТОРА Назначение и общие принципы выполнения защиты. ЗАЩИТА ОТ ЗАМЫКАНИЙ МЕЖДУ ВИТКАМИ ОДНОЙ ФАЗЫ Защита от витковых замыканий имеет ограниченное применение вследствие отсутствия простых способов ее осуществления. В связи с этим чувствительность защиты должна быть очень высокой и защита должна действовать на отключение.
24693. МАКСИМАЛЬНЫЕ ТОКОВЫЕ ЗАЩИТЫ С РЕЛЕ ПРЯМОГО ДЕЙСТВИЯ 557.5 KB
  Выпускаются токовые реле прямого действия мгновенные типа РТМ и с ограниченно зависимой характеристикой РТВ.32 а и б показаны двухфазные схемы МТЗ с реле типа РТВ. Реле РТВ представляет собой электромагнитное реле с втягивающимся якорем рис.
24694. НЕСЕЛЕКТИВНЫЕ ОТСЕЧКИ 45 KB
  Такая отсечка применяется для быстрого отключения КЗ в пределах всей защищаемой ЛЭП. Неселективное действие отсечки при КЗ вне ЛЭП исправляется при помощи АПВ включающего обратно отключившуюся ЛЭП. При этом пускается устройство АПВ которое включает обратно неселективно отключившуюся ЛЭП W1 и восстанавливает питание подстанции В.