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

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

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

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

Означення . Нехай 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 (modp ). Число 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₇ *: 3¹ = 3, 3² = 2, 3³ = 6, 3⁴ = 4, 3⁵ = 5, 3⁶ = 1.

log₃ 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_a k =(log_a b) (log_b k) modn

або

log_b k =(log_a k) (log_a b)^-1 modn.

З останньої рівності випливає справедливість теореми.

Примітивний алгоритм

Для знаходження log_g b (g – генератор G порядка n , b Î G) будемо обчислювати значення g , g ² , g ³ , g ⁴ , ... поки не отримаємо b . Часова оцінка алгоритму – O(n ). Якщо n – велике число, то час обчислення логарифму є достатньо великим і тому алгоритм є неефективним.

Алгоритм великого та малого кроку

Першим детермінованим алгоритмом для обчислення дискретного логарифму був алгоритм великого та малого кроку, запропонований Шанком (Shank) [1].

Для обчислення log_g b в групі Z_n ^* необхідно зробити наступні кроки:

1. Обчислити a = é ù ;

2. Побудувати списокL₁ = 1, g ^a , g ^{2 a} , ..., g (за модулем n );

3. Побудувати списокL₂ = b , bg , bg ² , ..., bg ^{a - 1} (за модулем n );

4. Знайти число z , яке зустрілося в L₁ та L₂ .

Тоді z = bg^k = g ^la для деяких k та l . Звідси b = g^{la - k} = g^x ; x = la - k .

Два питання постає при дослідженні роботи наведеного алгоритму:

1. Чи завжди знайдеться число, яке буде присутнім в обох списках?

2. Як ефективно знайти значення z?

Запишемо 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₂ , а справа – в L₁ .

Відсортуємо отримані списки L₁ та L₂ за час O(a * loga ). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z знайдене,

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать