Індекс числа по модулю
Дискретного логарифмування (DLOG) - задача звернення функції gx в деякій кінцевої мультиплікативної групі G.
Найбільш часто завдання діскетной логарифмирования розглядають в групі оборотних елементів кільця відрахувань. в мультиплікативної групі кінцевого поля. або в групі точок на еліптичній кривій над кінцевим полем. Ефективні алгоритми для вирішення завдання діскетной логарифмирования в загальному випадку невідомі.
Для заданих g і a рішення x рівняння gx = a називається дискретним логарифмом елемента a по підставі g. У разі, коли G є групою оборотних елементів кільця лишків за модулем m. рішення називають також індексом числа a за основою g. Індекс числа a за основою g гарантовано існує, якщо g є первісним коренем за модулем m.
Постановка задачі
Нехай в деякій кінцевої мультиплікативної абелевих групі G задано рівняння
Рішення завдання дискретного логарифмування полягає в знаходженні деякого цілого невід'ємного числа x. задовольняє рівняння (1). Якщо воно вирішується, у нього має бути хоча б одне натуральне рішення, яке не перевищує порядок групи. Це відразу дає грубу оцінку складності алгоритму пошуку рішень зверху - алгоритм повного перебору знайшов би рішення за число кроків, не вище порядку даної групи.
Найчастіше розглядається випадок, коли, тобто група є циклічною. породженої елементом g. У цьому випадку рівняння завжди має рішення. У разі ж довільної групи, питання про можливість розв'язання задачі дискретного логарифмування, тобто питання про існування рішень рівняння (1), вимагає окремого розгляду.
Найпростіше розглянути задачу дискретного логарифмування в кільці відрахувань по модулю простого числа.
Нехай задано порівняння
Будемо вирішувати задачу методом перебору. Випишемо таблицю всіх ступенів числа 3. Кожен раз ми обчислюємо залишок від ділення на 17 (наприклад, 3 3 ≡27 - залишок від ділення на 17 дорівнює 10).
Тепер легко побачити, що рішенням розглянутого порівняння є x = 4. оскільки 3 4 ≡13.
На практиці модуль зазвичай є досить великим числом, і метод перебору є занадто повільним, тому виникає потреба в більш швидких алгоритмах.
алгоритми рішення
У довільній мультипликативной групі
У кільці відрахувань по простому модулю
де p - просте, b не ділиться на p. Якщо a є утворюючим елементом групи, то рівняння (2) має рішення при будь-яких b. Такі числа a називаються ще первісних корінням. і їх кількість дорівнює φ (p - 1). де φ - функція Ейлера. Рішення рівняння (2) можна знаходити за формулою:
Однак, складність обчислення за цією формулою гірше, ніж складність перебору.
Наступний алгоритм має складність
- присвоїти
- знайти
- Скласти таблицю значень і впорядкувати її.
- Скласти таблицю значень і впорядкувати її.
- Знайти збіглися елементи з першої і другої таблиць. Для них
звідки - Видати.
Існує також безліч інших алгоритмів для вирішення задачі дискретного логарифмування в поле відрахувань. Їх прийнято розділяти на експоненціальні і субекспоненціальное. Полиномиального алгоритму для вирішення цього завдання поки не існує.
Алгоритми з експоненціальною складністю
- Алгоритм Шенкса (алгоритм великих і малих кроків. Baby-step giant-step)
- Алгоритм поліг-Хеллмана - працює, якщо відомо розкладання числа на прості множники. Складність:. Якщо множники, на які розкладається p - 1. досить маленькі, то алгоритм дуже ефективний.
- ρ-метод Полларда має евристичну оцінку складності.
субекспоненціальное алгоритми
Дані алгоритми мають складність арифметичних операцій, де і - деякі константи. Ефективність алгоритму багато в чому залежить від близькості c до 1 і d - до 0.
Найкращими параметрами в оцінці складності на даний момент є,.
Для чисел спеціального виду результат можна поліпшити. У деяких випадках можна побудувати алгоритм, для якого константи будуть,. За рахунок того, що константа c досить близька до 1, подібні алгоритми можуть обігнати алгоритм с.
У довільному кінцевому полі
Завдання розглядається в поле GF (q). де q = pn. p - просте.
- Алгоритм обчислення індексів (index-calculus) ефективний, якщо p невелика. У цьому випадку він має евристичну оцінку складності.
- Алгоритм Ель-Гамаля. що з'явився в 1985 році, можна застосувати при n = 2 і має складність арифметичних операцій.
- Алгоритм Копперсміта дискретного логарифмування в кінцевому полі характеристики 2 став першим субекспоненціальное алгоритмом дискретного логарифмування з константою в оцінки складності. Даний алгоритм з'явився в 1984 році - до винаходу решета числового поля.
У групі точок на еліптичній кривій
Розглядається група точок еліптичної кривої над кінцевим полем. У даній групі визначена операція додавання двох точок. Тоді mP - це. Рішенням задачі дискретного логарифмування на еліптичній кривій є знаходження такого натурального числа m. що
для заданих точок P і A.
Обчислювальна складність і додатки в криптографії
Завдання дискретного логарифмування є однією з основних задач, на яких базується криптографія з відкритим ключем. Ідея, що лежить в основі подібних систем, спирається на високу обчислювальну складність звернення деяких числових функцій. В даному випадку, операція дискретного логарифмування є зворотною до показової функції. Остання обчислюється досить просто, в той час як навіть найсучасніші алгоритми обчислення дискретного логарифма мають дуже високу складність, яка порівнянна з складністю найбільш швидких алгоритмів розкладання чисел на множники.
Інша можливість ефективного вирішення завдання обчислення дискретного логарифма пов'язана з квантовими обчисленнями. Теоретично доведено, що, використовуючи їх, дискретний логарифм може бути обчислений за поліноміальний час [2]. У будь-якому випадку, якщо поліноміальний алгоритм обчислення дискретного логарифма буде реалізований, це буде означати практичну непридатність криптосистем на його основі.
Класичними криптографічними схемами, що базуються на складності завдання дискретного логарифмування, є схема вироблення загального ключа Діффі-Хеллмана. схема електронного підпису Ель-Гамаля. криптосистема Мессі-Омури для передачі повідомлень.
Дивитися що таке "Індекс числа по модулю" в інших словниках:
ІНДЕКС - числа а по модулю т показник ув порівнянні a = gg (mod m), де АІ твзаімно прості, а g деякий фіксований первісний корінь по модулю т. І. числа апо модулю тобозначается через g = indg а чи, коротше, у = ind а. Первісні корені ... ... Математична енциклопедія
Числа Фібоначчі - Числа Фібоначчі елементи числової послідовності 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ... (послідовність A000045 в OEIS) в якій кожне наступне число дорівнює сумі двох ... ... Вікіпедія
Первісний корінь (теорія чисел) - Цей термін має також інші значення див. Первісний корінь. Первісний корінь по модулю m - ціле число g таке, що і при де - функція Ейлера. Іншими словами, первісний корінь це утворює елемент мультиплікативної ... Вікіпедія
Дискретного логарифмування - (DLOG) завдання звернення функції в деякій кінцевої мультиплікативної групі. Найбільш часто задачу дискретного логарифмування розглядають в мультиплікативної групі кільця відрахувань або кінцевого поля, а також в групі точок еліптичної ... ... Вікіпедія
Дискретний логарифм - Дискретне логарифмирование (DLOG) - задача звернення функції gx в деякій кінцевої мультиплікативної групі G. Найбільш часто завдання діскетной логарифмирования розглядають в групі оборотних елементів кільця відрахувань, в мультипликативной ... ... Вікіпедія
Двоїстість - 1) Д. в алгебраїчній геометрії подвійність між різними просторами когомологий на алгебраїч. многовидах. Когомологій когерентних пучків. Нехай X неособо проективне алгебраїч. різноманіття розмірності nнад алгебраїчно замкнутим ... Математична енциклопедія
Бра і кет - Цей термін має також інші значення див. Бра. <|> Bra ket бра кет ... Вікіпедія
Бра-кет - <|> bra ket бра кет Квантова механіка ... Вікіпедія
Кет-бра - <|> bra ket бра кет Квантова механіка ... Вікіпедія