.

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

Язык: украинский
Формат: реферат
Тип документа: Word Doc
389 2075
Скачать документ

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

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

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

Означення. Нехай 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

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020