Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.
История Маурис Крайчик первым предложил основную идею данного алгоритма в своей книге «Théorie des Nombres» в 1922 году. После 1976 года задача дискретного логарифмирования становится важной для математики и криптоанализа. Это связано с созданием криптосистемы Диффи-Хелмана. В связи с этим в 1977 году Р.Меркле возобновил обсуждения данного алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.
Постановка задачи дискретного логарифмирования Для заданного простого числа и двух целых чисел и требуется найти целое число , удовлетворяющее сравнению:
где является элементом циклической группы , порожденной элементом .
Алгоритм Вход: g — генератор циклической группы порядка n, a — из циклической подгруппы, p — простое число, c — параметр надёжности, обычно берут равным 10 или близкое к этому значению число (используется для реализации алгоритма на компьютере, если решает человек, то его не задают).
Задача: найти x такое, что .
Выбираем факторную базу S = {p1, p2, p3, …, pt} (Если G = Z*p, то база состоит из t первых простых чисел). Возводим g в случайную степень k, где k такое, что . Получаем . Представляем gk следующим образом:
где (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту. Из пункта 3 следует выражение
полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком). Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями. Выбираем случайное число k такое, что . Вычисляем . Повторяем пункт 3, только для числа . Если не получается, то возвращаемся к 6-му пункту. Аналогично пункту 4, получаем: , где (), где . В этом пункте мы и решили задачу дискретного логарифма, отыскав .
Выход: .
Пример Решить уравнение:
Выбираем факторную базу
Пусть k = 7 Вычисляем
Логарифмируем и обозначаем
И получаем систему уравнений
Решаем её
Действительно, , следовательно , ,
Находим k такое, чтобы
Следовательно
Логарифмируем данное выражение и получаем
Ответ:
Сложность В данном алгоритме, количество итераций зависит, как от размера p, так и от размера факторной базы. Но факторную базу мы выбираем заранее, и её размер является фиксированным. Поэтому итоговая сложность определяется только размером простого числа и равняется: , где , — некоторые константы, зависящие от промежуточных вычислений, в частности, от выбора факторной базы.
Усовершенствования Ускоренный алгоритм исчисления порядка, суть которого состоит в том, чтобы использовать таблицу индексов.
Сложность Вычислительная сложность снижена до , по сравнению с оригинальном алгоритмом.
См. также Дискретное логарифмирование Алгоритм Полига — Хеллмана Ρ-алгоритм Полларда Алгоритм COS
Ссылки http://refdb.ru/look/1629414-pall.html http://pratsi.opu.ua/app/webroot/articles/1414145386.pdf
Категория:Теоретико-числовые алгоритмы Категория:Теория групп