Реферат Збірник задач та вправ з алгебри (без розв'язку)


СкачатиСкачать (DOC|ZIP):
Збірник задач та вправ з алгебри (без розв'язку)

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

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

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

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


СкачатиСкачати:Збірник задач та вправ з алгебри (без розв'язку)


Схожі реферати:
  • Інвестиційний менеджмент: державне регулювання інвестиційного процесу Основні засади формування державної інвестиційнолї стр
  • РЕФЕРАТ на тему: Спорт та фізкультура ПЛАН 1. Місце спорту в житті людства 1. Місце спорту в житті людства, його функції та завдання
  • Провідні ідеї розвиненої схоластики ПЛАН 1. Загальна характеристика схоластики 2. Йоан Скот Еріугена 3. Ансельм Кентерберійс
  • Охарактеризувати структуру фінансових ресурсів та напрямки їх використання (реферат)
  • Курсова робота на тему: Господарський договір ПЛАН
  • ДИПЛОМНА РОБОТА на тему: Проблеми правового регулювання пенсійного забезпечення на Україні ЗМІСТ І. Вступ ІІ. Основна частина Правова при
  • Розвиток емпатії у студентів педагогічного вузу як майбутніх учителів ЗМІСТ ВСТУП РОЗДІЛ 1. ЕМПАТІЯ ВЧИТЕЛЯ У КОНТЕКСТІ ГУМАНН
  • КУРСОВА РОБОТА на тему: Помножувач частоти великої кратності міліметрового діапазону з малими втратами Зміст Вступ
  • ДuЦаЭЧ їЩy №nЧryptЭon Перший алгоритм кодування з відкритим ключем (ДuЦаЭЧ їЩy №nЧryptЭon, далі Дї№) було запропоновано Вітфілдом
  • РЕФЕРАТ на тему: Організація управління природоохоронної діяльності на обласному рівні Зміст 1. Вступ. 2. Загальна організація у




  • Скористайтеся пошуком:
    Loading

    Пошук :

    0.037528