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

💣 👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Проблема обчислення дискретного логарифма є не лише цікавою, а й вкрай корисною для систем захисту інформації. Ефективний алгоритм знаходження дискретного логарифму значною мірою знизив би безпеку систем ідентифікації користувача та схеми обміну ключей.
Означення
. Нехай G – скінченна циклічна група порядка n
. Нехай g
– генератор G та b
Î G. Дискретним логарифмом

числа b
за основою g
називається таке число x (0 £ x
£ n
- 1), що g x

= b
та позначається x = log g
b
.
Проблема дискретного логарифму.
Нехай p
– просте число, g
– генератор множини Z p

*
, y
ÎZ p

*
. Знайти таке значення x
(0 £ x
£ p
- 2), що g x

º y
(mod p
). Число x
називається дискретним логарифмом

числа yза основою g та модулем p
.
Узагальнена проблема дискретного логарифму.
Нехай G – скінченна циклічна група порядка n, g
– її генератор, b
Î G. Необхідно знайти таке число x
(0 £ x
£ n
- 1), що g x

= b
.
Розширенням узагальненої проблеми може стати задача розв’язку рівняння g
x

= b
, коли знято умову циклічності групиG, а також умову того, що g
– генератор G (в такому випадку рівняння може і не мати розв’язку).
Приклад.
g
= 3 є генератором Z 7
*: 3 1
= 3, 3 2
= 2, 3 3
= 6, 3 4
= 4, 3 5
= 5, 3 6
= 1.
log 3
4 = 4 (mod 7), тому що розв’язком рівняння 3 x
= 4 буде x = 4.
Теорема.
Нехай а
– генератор скінченної циклічної групи G порядка n. Якщо існує алгоритм, який обчислює дискретний логарифм за основою а
, то цей алгоритм може також обчислити дискретний логарифм за будь-якою основою b
, яка є генератором G.
Доведення. Нехай k
ÎG, x = log a
k
, y = log b
k
, z = log a
b
. Тоді a
x
= b
y
= ( a
z
) y
, звідки x = zymodn. Підставимо в останню рівність замість змінних логарифмічні вирази:
log b
k =(log a

k) (log a

b) -1
modn.
З останньої рівності випливає справедливість теореми.
Для знаходження log g
b
(g – генератор G порядка n
, b
Î G) будемо обчислювати значення g
, g
2
, g
3
, g
4
, ... поки не отримаємо b
. Часова оцінка алгоритму – O( n
). Якщо n
– велике число, то час обчислення логарифму є достатньо великим і тому алгоритм є неефективним.
Першим детермінованим алгоритмом для обчислення дискретного логарифму був алгоритм великого та малого кроку, запропонований Шанком (Shank) [1].
Для обчислення log g
b
в групі Z n

*
необхідно зробити наступні кроки:
2. Побудувати списокL 1
= 1, g
a

, g
2
a

, ..., g
(за модулем n
);
3. Побудувати списокL 2
= b
, bg
, bg
2
, ..., bg
a

- 1
(за модулем n
);
4. Знайти число z
, яке зустрілося в L 1
та L 2
.
Тоді z
= bg k

= g
la

для деяких k
та l
. Звідси b
= g la

-

k

= g x

; x
= la
- k
.
Два питання постає при дослідженні роботи наведеного алгоритму:
1. Чи завжди знайдеться число, яке буде присутнім в обох списках?
Запишемо x
= s
a
+ t
для деяких s
, t
таких що 0 £ s
, t
< a
. Тоді b
= g x

= g s

a

+
t
. Домножимо рівність на g
a

-
t

, отримаємо: bg
a

-
t
= g s

(
a

+ 1)
. Значення зліва обов’язково зустрінеться в L 2
, а справа – в L 1
.
Відсортуємо отримані списки L 1
та L 2
за час O( a
* log a
). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z
знайдене, якщо ні – то видалити менше число і продовжити перевірку.
Приклад.
Розв’язати рівняння: 2 x
º 11 (mod 13).
L 1
: 1, 2 4
º 3, 2 8
º 9, 2 12
º 1, 2 16
º 3;
L 2
: 11, 11 * 2 º 9, 11 * 2 2
º 5, 11 * 2 3
º 10;
Число 9 зустрілося в обох списках. 11 * 2 º 2 8
, 11 º 2 7
, звідки x
= 7.
Інший підхід до реалізації алгоритму великого та малого кроку можна отримати якщо рівність b
= g s

a

+
t

( a
= é ù , 0 £ s
, t
< a
) переписати у вигляді b
* (g -
a

) s

= g t

. Обчислимо g
-
a

та складемо таблицю значень g t

, 0£ t
< a
. Далі починаємо знаходити значення b
* (g -
a

) s

, s
= 0, 1, … перевіряючи їх наявність у таблиці g t

. Як тільки знаходяться такі s
та t
, алгоритм зупиняється.
Приклад.
Обчислити log 2
3 в групі Z 19
*
.
3 = 2 x
= 2 sa

+1
, 3 * (2 - a

) s

= 2 t

. Складемо таблицю 2 t

, 0£ t
< é ù = 5:
2 -1
º 10 (mod 19), оскільки 2 * 10 º 1 (mod 19).
Тоді 3 * (2 -
5
) s

(mod 19) º 3 * (10 5
) s
(mod 19) º 3 * 3 s

(mod 19)
Значення 8, яке отримали при s = 2, присутнє в таблиці 2 t

, 0£ t
< 5.
Звідси3 * (2 -
5
) 2
= 2 3
або 3 = (2 5
) 2
* 2 3
= 2 5*2+3
= 2 13
.
Відповідь: 3 = 2 13
, тобто log 2
3 = 13.
Нехай G – циклічна група з порядком n
( n
– просте). Розіб’ємо елементи групи G на три підмножини S 1
, S 2
та S 3
, які мають приблизно однакову потужність. При цьому необхідне виконання умови: 1 Ï S 2
. Визначимо послідовність елементів x
i
наступним чином:
Ця послідовність у свою чергу утворить дві послідовності c
i
та d
i
, що задовольняють умові
Алгоритм буде працювати циклічно шукаючи таке знчення i
, для якого x
i
= x
2
i
. Для таких значень будуть мати місце рівність = або = . Логарифмуючи останню рівність за основою a
, матимемо:
( d
i
- d
2i
) * log a
b
º ( c
2i
- c
i
) mod n

Якщо d
i
¹ d
2
i
(modn), то це рівняння може бути ефективно розв’язано для обчислення log a
b
.
Вхід: генератор a
циклічної групи G з порядком nта елемент b
Î G.
Вихід: дискретний логарифм x = log a
b
.
2.1. За значеннями x i

-1
, c i

-1
, d i

-1
та x
2
i

-2
, c
2
i

-2
, d
2
i

-2
обчислити значення x i

, c i

, d i

та x
2
i

, c
2
i

, d
2
i

використовуючи формули (1), (2), (3).
if ( r
= 0) thenreturn (FALSE); // розв’язку не знайдено
Якщо алгоритм завершується невдачею (повертає FALSE), то можна запустити його вибравши інші початкові значення c
0
, d
0
з інтервалу [1; n
- 1] та поклавши x 0
= .
Приклад.
Обчислити log 2
9в групі Z 19
*
.
На 6 кроці отримали x 6
= x 12
. Підставивши їх значення, отримаємо:
2 8
* 9 6
= 2 64
* 9 62
або 2 8 – 64
= 9 62 – 6
, 2 -56
= 9 56

Логарифмуємо рівність: -56 * log 2
9 = 56 (mod 18), оскільки |Z 19
*
| = 18.
Враховуючи що -56 (mod 18) º 16, 56 (mod 18) º 2, перепишемо рівність у вигляді 16 * log 2
9 = 2 (mod 18) або 8 * log 2
9 = 1 (mod 9). log 2
9 = 8 -1
(mod 9) = 8.
Алгоритм, базований на обчисленні індексів, є найпотужним при обчисленні дискретного логарифму. Необхідно побудувати відносно невелику підмножину S елементів групи G, яка називається множниковою основою

. Ця підмножина повинна обиратися таким чином, щоб як можна більша частина елементів G могла бути представлена у вигляді добутку її елементів. При обчисленні значення log a
b
( a
– генератор G, b
Î G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b
.
Вхід: генератор a
циклічної групи G порядка n та елемент b
Î G.
Вихід: дискретний логарифм x
= log a
b
.
1. Побудувати множину S – множникову основу. Нехай S = { p
1
, p
2
, …, p t

}. В якості значень p i

можна обрати, наприклад, i
- те просте число.
2. Побудувати систему лінійних рівнянь, розв’язком якої будуть значення log a

p i
. Для цього виконаємо наступні кроки:
2.1. Обрати деяке ціле k
, 0 £ k
£ n
- 1 та обчислити a k

.
2.2. Спробувати представити значення a k

у вигляді добутку чисел з S:
Якщо така рівність знайдена, то записати рівняння:
2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t
+ c
лінійних рівнянь. Невелике ціле число c
(1 £ c
£ 10) обирається таким чином, щоб складена система рівнянь мала єдиний розв’язок з великою ймовірністю (якщо скласти лише t
рівнянь з t
невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв’язку).
3. Розв’язати утворену систему рівнянь, отримати значення log a
p i

, 1£ i
£ t
.
4.1. Обрати деяке ціле k
, 0 £ k
£ n
- 1 та обчислити b
* a k

.
4.2. Спробувати представити значення b
* a k

у вигляді добутку чисел з S:
Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:
Приклад.
Обчислити log 2
12 в групі Z 19
*
.
1. Нехай S = {2, 3, 5} – множникова основа.
2. Будуємо систему рівнянь для знаходження значень log 2
p i

, де p i

ÎS. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.
k
= 5: 2 5
(mod 19) º13 – не представимо у вигляді добутку чисел з S.
k
= 7: 2 7
(mod 19) º14 – не представимо у вигляді добутку чисел з S.
k
= 2: 2 2
(mod 19) º4 = 2 2
. Перше рівняння: 2 = 2log 2
2.
k
= 10: 2 10
(mod 19) º17 – не представимо у вигляді добутку чисел з S.
k
= 15: 2 15
(mod 19) º12 = 2 2
* 3. Друге рівняння: 15 = 2log 2
2 + log 2
3.
k
= 11: 2 11
(mod 19) º15 = 3 * 5. Третє рівняння: 11 = log 2
3 + log 2
5.
3. Система рівнянь за модулем 18 (порядок Z 19
*
дорівнює 18) має вигляд:
log 2
2 = 1, log 2
3 = 13, log 2
5 = 16
k
= 3: 12 * 2 3
(mod 19) º 1 – не представимо у вигляді добутку чисел з S.
k
= 7: 12 * 2 7
(mod 19) º16 = 2 4
.
log 2
12 + 7 º 4log 2
2 (mod 18), log 2
12 º (4log 2
2 – 7) (mod 18) = 15.
Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n
, якщо число n
має лише малі прості дільники.
Нехай g
, h
ÎG, |G| = p s

, p
– просте. Тоді значення x
= log g
h
можна подати у вигляді:
x
= x
0
+ x
1
p
+ x
2
p
2
+ … + x s

-1
p s

-1

Піднесемо рівняння h
= g x

до степеня p s

-1
:
оскільки = 1 ( g
– генератор групи, p s

– її порядок).
Таким чином з рівності = знаходимо x
0
.
Далі маючи значення x
0
, x
1
, …, x i

-1
можна обчислити x i

з рівняння
Приклад.
Обчислити log 3
7 в Z 17
*
.
Необхідно розв’язати рівняння 3 x

= 7 в групі, порядок якої дорівнює 16 = 2 4
.
Представимо x
у двійковій системі числення: x
= x
0
+ 2 x
1
+ 4 x
2
+ 8 x
3
.
Піднесемо рівняння 3 x

= 7 до степеня 2 3
= 8:
Оскільки 3 16
(mod 17) º 1, тоостаннє рівняння прийме вигляд = -1. Враховуючи що 3 8
(mod 17) º -1, маємо: = -1, x
0
= 1.
Домножимо рівність = 7 на = 3 -1
(mod 17) = 6, отримаємо:
Піднесемо рівняння до степеня 4: = 8 4
, = -1, x 1
= 1.
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.

Название: Дискретний логарифм
Раздел: Рефераты по астрономии
Тип: реферат
Добавлен 20:03:23 29 января 2011 Похожие работы
Просмотров: 6
Комментариев: 13
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Дискретний логарифм
Реферат: Судебное разбирательство в уголовном процессе
Лабораторная Работа Класс Насекомых
Реферат: Народовластие как идея политической социализации
Лекция по теме Метаболизм гема
Сочинение На Тему Времена Года
Реферат На Тему Міжнародна Технічна Допомога Та Її Роль У Розвитку Економіки України
Курсовая работа по теме Формирование качества сыров
Реферат по теме Идеи философии Сократа
Применение Линзы Френеля В Маяках Реферат
Реферат: Walt Disney Essay Research Paper Walt DisneyWhen
Дипломная работа: Информационные технологии при анализе бизнеса. Скачать бесплатно и без регистрации
Курсовая работа по теме Товароведная характеристика фотоаппаратов
Контрольная Работа 2 Диктант 8 Класс
Итоговое Сочинение Забвение Прошлого Грозит Его Повторением
Сотрудник Полиции Эссе
Учебное пособие: Виконання операцій множення і ділення у двійковій системі числення
Дипломная работа по теме Разработка техпроцесса механической обработки детали
11 Класс Контрольная Работа 1 Четверть Бим
Реферат: Коммуникации в управлении маркетингом. Скачать бесплатно и без регистрации
Дипломная работа по теме Идентификация и диагностика систем
Реферат: Договор перевозки грузов 5
Реферат: Звуки, питающие мозг энергией
Реферат: Таможенные режимы 3