Interested Article - Алгоритм исчисления порядка

Алгоритм исчисления порядка ( index-calculus algorithm ) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа . На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией . Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер . Примером такого алгоритма является ГОСТ Р 34.10-2012 .

История

Маурис Крайчик первым предложил основную идею данного алгоритма в своей книге «Théorie des Nombres» в 1922 году. После 1976 года задача дискретного логарифмирования становится важной для математики и криптоанализа. Это связано с созданием криптосистемы Диффи-Хелмана . В связи с этим в 1977 году Р.Меркле возобновил обсуждения данного алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.

Постановка задачи дискретного логарифмирования

Для заданного простого числа и двух целых чисел и требуется найти целое число , удовлетворяющее сравнению:

где является элементом циклической группы , порожденной элементом .

Алгоритм

Вход : g — генератор циклической группы порядка n , a — из циклической подгруппы, p — простое число, c — параметр надёжности, обычно берут равным 10 или близкое к этому значению число (используется для реализации алгоритма на компьютере, если решает человек, то его не задают).

Задача : найти x такое, что .

  1. Выбираем факторную базу S = { p 1 , p 2 , p 3 , …, p t } (Если G = Z * p , то база состоит из t первых простых чисел).
  2. Возводим g в случайную степень k , где k такое, что . Получаем .
  3. Представляем g k следующим образом:
    где (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.
  4. Из пункта 3 следует выражение
    полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а в группе G ). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).
  5. Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.
  6. Выбираем случайное число k такое, что . Вычисляем .
  7. Повторяем пункт 3, только для числа . Если не получается, то возвращаемся к 6-му пункту.
  8. Аналогично пункту 4, получаем:
    , где ( ), где . В этом пункте мы и решили задачу дискретного логарифма, отыскав .

Выход : .

Пример

Решить уравнение:

Выбираем факторную базу Пусть k = 7 Вычисляем

Логарифмируем и обозначаем И получаем систему уравнений

Решаем её

Действительно, , следовательно , ,

Находим k такое, чтобы

Следовательно

Логарифмируем данное выражение и получаем

Ответ :

Сложность

В данном алгоритме, количество итераций зависит, как от размера p , так и от размера факторной базы. Но факторную базу мы выбираем заранее, и её размер является фиксированным. Поэтому итоговая сложность определяется только размером простого числа и равняется: , где , — некоторые константы, зависящие от промежуточных вычислений, в частности, от выбора факторной базы.

Усовершенствования

, суть которого состоит в том, чтобы использовать таблицу индексов.

Сложность

Вычислительная сложность снижена до , по сравнению с оригинальном алгоритмом.

См. также

Ссылки

Источник —

Same as Алгоритм исчисления порядка