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

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

Описание

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

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

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

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

На втором этапе решается система линейных уравнений для вычисления дискретных логарифмов факторной базы. Система сотен тысяч или миллионов уравнений представляет собой серьезное вычисление, требующее больших объемов памяти, и она не является смущающе параллельной, поэтому суперкомпьютер обычно используется . Это считалось незначительным шагом по сравнению с другими для небольших вычислений дискретного журнала. Однако более крупные записи дискретного логарифма стали возможными только за счет переноса работы с линейной алгебры на сито (т. е. увеличения количества уравнений при уменьшении числа переменных).

На третьем этапе осуществляется поиск мощности s генератора g , которую при умножении на аргумент h можно разложить по факторной базе g. ^с ч = (−1) ^{ж ₀} 2 ^{ж ₁} 3 ^f_f2 ··· п _р ^{фр _р} .

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

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

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

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

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

Алгоритм

Вход: генератор дискретных логарифмов. $g$, модуль $q$ и аргумент $h$. Факторная база $\{-1,2,3,5,7,11,\ldots ,p_{r}\}$, длины $r+1$.
Выход: $x$ такой, что $g^{x}=h\mod q$.

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

Сложность

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

История

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

Семейство индексного исчисления

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

Внешние ссылки

• Дискретные логарифмы в конечных полях и их криптографическое значение , Эндрю Одлызко.
• Задача дискретного логарифма Криса Стадхолма, включая статью от 21 июня 2002 г. «Проблема дискретного логарифма».
• А. Менезес; П. ван Оршот; С. Ванстон (1997). Справочник по прикладной криптографии . ЦРК Пресс . стр. 107–109 . ISBN  0-8493-8523-7 .