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.


 

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

18634. Определение корпоративной информационной системы. Основ¬ные принципы комплексной автоматизации предприятия 14.45 KB
  Определение корпоративной информационной системы. Основные принципы комплексной автоматизации предприятия. КИС комплекс программ или программная система обеспечивающая основные бизнеспроцессы в компании. Корпоративной информационной системой КИС мы будем...
18635. Интерфейс: ввода/вывода, справочный 17.96 KB
  Интерфейс: ввода/вывода справочный. Связь пользователя с программами пакета можно представить как обмен сообщениями: либо пользователь передает в пакет некоторый запрос и получает на него ответ либо запрос формируется в пакете а от пользователя ожидается ответ. Для в
18636. Функции менеджмента 16.09 KB
  Функции менеджмента. Функции менеджмента являются составными частями любого процесса управления вне зависимости от особенностей размера назначения формы собственности и т.д. той или иной организации. Процесс управления менеджмента имеет пять взаимосвязанных функ
18637. Нейронные сети. Распознавание образов 542 KB
  Основные задачи, которые ставятся перед нейронными сетями, относятся к задачам распознавания образов. Они заключаются в том, чтобы классифицировать входной образ, то есть отнести его к какому-либо известному сети классу. Изначально сети даются эталонные образы – такие образы...
18638. Структурные единицы ЭВМ – элементы, узлы, блоки, устройства. Приведите примеры 13.85 KB
  Структурные единицы ЭВМ элементы узлы блоки устройства. Приведите примеры. Для составления полного представления о структуре ЭВМ необходимо рассмотреть ее элементную базу. Обычно при детализации структуры ЭВМ выделяют следующие структурные функциональные единицы...
18639. Анализ деловой активности предприятия 14.71 KB
  Анализ деловой активности предприятия Анализ деловой активности предприятия можно провести по следующим показателям: качественные показатели количественные показатели. 1.На качественном уровне предполагает анализ по так называемым неформализуемым критериям. Ре
18640. Организация связи предприятия с внешним миром 13.87 KB
  Организация связи предприятия с внешним миром. Виды связей организации с внешним окружением. Связи организации с внешней средой весьма трудно классифицировать вопервых ввиду их многофункциональности. Так властная регламентирующая связь может одновременно быть инф
18641. Технологии описания бизнес-процессов 15.63 KB
  Технологии описания бизнеспроцессов. Технология описания бизнеспроцессов была разработана на заре рождения процессноориентированного подхода к управлению первоначально она состояла всего лишь из двух стандартов описания бизнеспроцессов DFD и WFD IDEF3 которые испол...
18642. Цена – микс 14.18 KB
  Цена микс. Оперативнотактические инструменты ценообразования это большая группа средств ценовой политики позволяющая решать краткосрочные стратегические задачи а также оперативно реагировать на неожиданные изменения различных факторов ценообразования или агр...