Алгоритм расчета индекса

В теории вычислений чисел , то алгоритм индекса Исчисления является вероятностным алгоритмом для вычисления дискретных логарифмов . Посвященный дискретному логарифму в где - простое число, исчисление индекса приводит к семейству алгоритмов, адаптированных к конечным полям и некоторым семействам эллиптических кривых. Алгоритм собирает отношения между дискретными логарифмами малых простых чисел, вычисляет их с помощью процедуры линейной алгебры и, наконец, выражает желаемый дискретный логарифм относительно дискретных логарифмов малых простых чисел.${\ Displaystyle (\ mathbb {Z} / д \ mathbb {Z}) ^ {*}}$${\ displaystyle q}$

Описание [ править ]

Грубо говоря, задача дискретного логарифма требует от нас найти такое x , что , где даны g , h и модуль n .${\ Displaystyle г ^ {х} \ эквив ч {\ pmod {п}}}$

Алгоритм (подробно описанный ниже) применяется к группе, где q простое число. В качестве входных данных требуется факторная база . Эта факторная база обычно выбирается в виде числа −1 и первых r простых чисел, начинающихся с 2. С точки зрения эффективности мы хотим, чтобы эта факторная база была небольшой, но для решения дискретного журнала для большой группы мы требуем, чтобы факторная база была (относительно) большой. В практических реализациях алгоритма эти противоречивые цели так или иначе ставятся под угрозу.${\ Displaystyle (\ mathbb {Z} / д \ mathbb {Z}) ^ {*}}$

Алгоритм выполняется в три этапа. Первые два этапа зависит только от генератора г и простого модуль д , и найти дискретные логарифмы в факторе основание из г малых простых чисел. На третьем этапе осуществляется поиск дискретного логарифма желаемого числа h в терминах дискретных логарифмов факторной базы.

Первый этап состоит в поиске набора r линейно независимых соотношений между факторной базой и мощностью генератора g . Каждое отношение способствует одно уравнения к системе линейных уравнений в г неизвестных, а именно дискретных логарифмы г простых чисел в факторе основании. Этот этап до неприличия параллелен, и его легко разделить между множеством компьютеров.

На втором этапе решается система линейных уравнений для вычисления дискретных логарифмов факторной базы. Система из сотен тысяч или миллионов уравнений - это серьезное вычисление, требующее большого количества памяти, и оно не является слишком параллельным, поэтому обычно используется суперкомпьютер . Это считалось незначительным шагом по сравнению с другими для небольших дискретных вычислений журнала. Однако более крупные записи дискретных логарифмов ^{[1] [2]} стали возможными только за счет смещения работы с линейной алгебры на решето (т. Е. Увеличения количества уравнений при уменьшении количества переменных).

На третьем этапе выполняется поиск мощности s генератора g, которая при умножении на аргумент h может быть разложена на множители g ^s h = (−1) ^{f ₀} 2 ^{f ₁} 3 ^{f ₂} ··· p _r ^{f _r} .

Наконец, в операции, слишком простой, чтобы ее можно было назвать четвертым этапом, результаты второго и третьего этапов могут быть перегруппированы с помощью простых алгебраических манипуляций для получения желаемого дискретного логарифма x = f ₀ log _g (−1) + f ₁ журнал _г 2 + е ₂ журнал _г 3 + ··· + ф _р журнал _г п _р - с .

Первый и третий этапы до неприличия параллельны, и на самом деле третий этап не зависит от результатов первых двух этапов, поэтому его можно проводить параллельно с ними.

Выбор размера факторной базы r имеет решающее значение, и его детали слишком сложны, чтобы объяснять их здесь. Чем больше факторная база, тем легче найти отношения на этапе 1 и тем легче завершить этап 3, но тем больше связей вам потребуется, прежде чем вы сможете перейти к этапу 2, и тем сложнее этап 2. Относительная доступность компьютеров, подходящих для различных типов вычислений, необходимых для этапов 1 и 2, также важна.

Приложения в других группах [ править ]

Отсутствие понятия простых элементов в группе точек на эллиптических кривых делает невозможным найти эффективную факторную базу для выполнения метода исчисления индекса, представленного здесь в этих группах. Следовательно, этот алгоритм не может эффективно решать дискретные логарифмы в группах эллиптических кривых. Однако: для особых видов кривых (так называемых суперсингулярных эллиптических кривых ) существуют специализированные алгоритмы для решения проблемы быстрее, чем с помощью общих методов. Хотя использования этих специальных кривых можно легко избежать, в 2009 году было доказано, что для некоторых полей проблема дискретного логарифмирования в группе точек на общихэллиптические кривые над этими полями могут быть решены быстрее, чем с помощью общих методов. Алгоритмы действительно являются адаптацией метода исчисления индексов. ^[3]

Алгоритм [ править ]

Вход: генератор дискретного логарифма g , модуль q и аргумент h . Факторная база {−1,2,3,5,7,11, ..., p _r } длины r  + 1.
Выведите: x такой, что g ^x ≡ h (mod q ).

• отношения ← empty_list
• для k = 1, 2, ...
  • Используя алгоритм целочисленной факторизации , оптимизированный для гладких чисел , попробуйте разложить на множители (евклидов остаток) с использованием факторной базы, т.е. найти такие, что${\ displaystyle g ^ {k} {\ bmod {q}}}$${\ displaystyle e_ {i}}$${\displaystyle g^{k}{\bmod {q}}=(-1)^{e_{0}}2^{e_{1}}3^{e_{2}}\cdots p_{r}^{e_{r}}}$
  • Каждый раз, когда обнаруживается факторизация:
    • Сохраните k и вычисленные как вектор (это называется отношением)${\displaystyle e_{i}}$${\displaystyle (e_{0},e_{1},e_{2},\ldots ,e_{r},k)}$
    • Если это отношение линейно не зависит от других отношений:
      • Добавить в список отношений
      • Если существует не менее r  + 1 отношений, выйдите из цикла
• Сформируйте матрицу, строки которой являются отношениями
• Получить приведенную эшелонированную форму матрицы
  • Первый элемент в последнем столбце - это дискретный логарифм -1, а второй элемент - дискретный логарифм 2 и т. Д.
• для s = 1, 2, ...
  • Попытайтесь учесть факторную базу${\displaystyle g^{s}h{\bmod {q}}=(-1)^{f_{0}}2^{f_{1}}3^{f_{2}}\cdots p_{r}^{f_{r}}}$
  • Когда факторизация найдена:
    • Выход ${\displaystyle x=f_{0}\log _{g}(-1)+f_{1}\log _{g}2+\cdots +f_{r}\log _{g}p_{r}-s.}$

Сложность [ править ]

Предполагая оптимальный выбор факторной базы, ожидаемое время работы (с использованием L-нотации ) алгоритма расчета индекса может быть указано как .${\displaystyle L_{n}[1/2,{\sqrt {2}}+o(1)]}$

История [ править ]

Основная идея алгоритма принадлежит Вестерну и Миллеру (1968), ^[4], который в конечном итоге опирается на идеи Крайчика (1922). ^[5] Первые практические реализации последовали за введением в 1976 году криптосистемы Диффи-Хеллмана, основанной на дискретном логарифме. Диссертация Меркла в Стэнфордском университете (1979) была одобрена Полигом (1977) и Хеллманом и Рейнери (1983), которые также внесли улучшения в реализацию. ^{[6] [7]} Адлеман оптимизировал алгоритм и представил его в нынешнем виде. ^[8]

Семейство Index Calculus [ править ]

Индексное исчисление вдохновило большое семейство алгоритмов. В конечных полях с для некоторых простых , Состояния-техники алгоритмы решета числового поля для дискретных логарифмов, когда велик по сравнению с , в функции поле сита , и Ж, ^[9] для , когда мал по сравнению с и решето числового поля в высокой степени, для когда среднеспелая сторона. Дискретный логарифм в некоторых семействах эллиптических кривых может быть решен за время для , но общий случай остается экспоненциальным.${\displaystyle \mathbb {F} _{q}}$${\displaystyle q=p^{n}}$${\displaystyle p}$${\displaystyle L_{q}\left[1/3,{\sqrt[{3}]{64/9}}\,\right]}$${\displaystyle p}$${\displaystyle q}$${\displaystyle L_{q}\left[1/3,{\sqrt[{3}]{32/9}}\,\right]}$ ${\displaystyle L_{q}\left[1/4+\varepsilon ,c\right]}$${\displaystyle c>0}$${\displaystyle p}$${\displaystyle q}$${\displaystyle L_{q}[1/3,c]}$${\displaystyle c>0}$${\displaystyle p}$${\displaystyle L_{q}\left[1/3,c\right]}$${\displaystyle c>0}$

Внешние ссылки [ править ]

• Дискретные логарифмы в конечных полях и их криптографическое значение , Андрей Одлызко
• Задача дискретного логарифма Криса Студхолма, включая статью 21 июня 2002 г. «Проблема дискретного логарифма».
• А. Менезес, П. ван Оршот, С. Ванстон (1997). Справочник по прикладной криптографии . CRC Press . С.  107–109 . ISBN 0-8493-8523-7.CS1 maint: uses authors parameter (link)

Заметки [ править ]