UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75838
останнє поновлення: 2016-12-03
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваДискретний логарифм (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1799
Скачало384
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

Проблема обчислення дискретного логарифма є не лише цікавою, а й вкрай

корисною для систем захисту інформації. Ефективний алгоритм знаходження

дискретного логарифму значною мірою знизив би безпеку систем

ідентифікації користувача та схеми обміну ключей.

 

Означення. Нехай 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* необхідно зробити наступні кроки:

 

???;

 

(за модулем 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). За лінійний

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ