В теории вычислений чисел , то алгоритм индекса Исчисления является вероятностным алгоритмом для вычисления дискретных логарифмов . Посвященный дискретному логарифму в где - простое число, исчисление индекса приводит к семейству алгоритмов, адаптированных к конечным полям и некоторым семействам эллиптических кривых. Алгоритм собирает отношения между дискретными логарифмами малых простых чисел, вычисляет их с помощью процедуры линейной алгебры и, наконец, выражает желаемый дискретный логарифм относительно дискретных логарифмов малых простых чисел.
Описание [ править ]
Грубо говоря, задача дискретного логарифма требует от нас найти такое x , что , где даны g , h и модуль n .
Алгоритм (подробно описанный ниже) применяется к группе, где q простое число. В качестве входных данных требуется факторная база . Эта факторная база обычно выбирается в виде числа −1 и первых r простых чисел, начинающихся с 2. С точки зрения эффективности мы хотим, чтобы эта факторная база была небольшой, но для решения дискретного журнала для большой группы мы требуем, чтобы факторная база была (относительно) большой. В практических реализациях алгоритма эти противоречивые цели так или иначе скомпрометированы.
Алгоритм выполняется в три этапа. Первые два этапа зависит только от генератора г и простого модуль д , и найти дискретные логарифмы в факторе основание из г малых простых чисел. На третьем этапе осуществляется поиск дискретного логарифма желаемого числа h в терминах дискретных логарифмов факторной базы.
Первый этап состоит в поиске набора r линейно независимых соотношений между факторной базой и мощностью генератора g . Каждое отношение способствует одно уравнения к системе линейных уравнений в г неизвестных, а именно дискретных логарифмы г простых чисел в факторе основании. Этот этап до неприличия параллелен, и его легко разделить между множеством компьютеров.
На втором этапе решается система линейных уравнений для вычисления дискретных логарифмов факторной базы. Система из сотен тысяч или миллионов уравнений - это серьезное вычисление, требующее большого количества памяти, и оно не является слишком параллельным, поэтому обычно используется суперкомпьютер . Это считалось незначительным шагом по сравнению с другими для небольших дискретных вычислений журнала. Однако более крупные записи дискретных логарифмов [1] [2] стали возможными только за счет смещения работы с линейной алгебры на решето (т. Е. Увеличения количества уравнений при уменьшении количества переменных).
На третьем этапе выполняется поиск мощности s генератора g, которая при умножении на аргумент h может быть разложена на множители g s h = (−1) f 0 2 f 1 3 f 2 ··· p r f r .
Наконец, в операции, слишком простой, чтобы ее можно было назвать четвертым этапом, результаты второго и третьего этапов могут быть перегруппированы с помощью простых алгебраических манипуляций для вычисления желаемого дискретного логарифма x = f 0 log g (−1) + f 1 журнал г 2 + е 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, ...
- Используя алгоритм целочисленной факторизации , оптимизированный для гладких чисел , попробуйте разложить на множители (евклидов остаток), используя факторную базу, т.е. найдите такие, что
- Каждый раз, когда обнаруживается факторизация:
- Сохраните k и вычисленные как вектор (это называется отношением)
- Если это отношение линейно не зависит от других отношений:
- Добавить в список отношений
- Если существует не менее r + 1 отношений, выйдите из цикла
- Сформируйте матрицу, строки которой являются отношениями
- Получить приведенную эшелонированную форму матрицы
- Первый элемент в последнем столбце - это дискретный логарифм -1, а второй элемент - дискретный логарифм 2 и т. Д.
- для s = 1, 2, ...
- Попытайтесь учесть факторную базу
- Когда факторизация найдена:
- Выход
Сложность [ править ]
Предполагая оптимальный выбор факторной базы, ожидаемое время работы (с использованием L-нотации ) алгоритма расчета индекса может быть указано как .
История [ править ]
Основная идея алгоритма принадлежит Вестерну и Миллеру (1968), [4], который в конечном итоге опирается на идеи Крайчика (1922). [5] Первые практические реализации последовали за введением в 1976 году криптосистемы Диффи-Хеллмана, основанной на дискретном логарифме. Диссертация Меркла в Стэнфордском университете (1979) была одобрена Полигом (1977) и Хеллманом и Рейнери (1983), которые также внесли улучшения в реализацию. [6] [7] Адлеман оптимизировал алгоритм и представил его в нынешнем виде. [8]
Семейство Index Calculus [ править ]
Индексное исчисление вдохновило большое семейство алгоритмов. В конечных полях с для некоторых простых , Состояния-техники алгоритмы решета числового поля для дискретных логарифмов, когда велик по сравнению с , в функции поле сита , и Ж, [9] для , когда мал по сравнению с и решето числового поля в высокой степени, для когда среднеспелая сторона. Дискретный логарифм в некоторых семействах эллиптических кривых может быть решен за время для , но общий случай остается экспоненциальным.
Внешние ссылки [ править ]
- Дискретные логарифмы в конечных полях и их криптографическое значение , Андрей Одлызко
- Задача дискретного логарифма Криса Студхолма, включая статью « Проблема дискретного логарифма» от 21 июня 2002 г.
- А. Менезес, П. ван Оршот, С. Ванстон (1997). Справочник по прикладной криптографии . CRC Press . С. 107–109 . ISBN 0-8493-8523-7.CS1 maint: uses authors parameter (link)
Заметки [ править ]
- ^ Торстен Kleinjung, Клаус Дием, Арлен К. Ленстр, Кристин Priplata, Колин Stahlke, «Вычисление 768-битового простое поле дискретного логарифма» , МАКИ Спринт, 2017
- ^ Джошуа Фрид, Пьеррик Годри, Надя Хенингер, Эммануэль Том, «Вычисление дискретного логарифма килобитных скрытых snfs» , весна IACR, июль 2016 г.
- Перейти ↑ Diem, C (2010). «К проблеме дискретного логарифмирования в эллиптических кривых». Compositio Mathematica .
- ^ Вестерн и Миллер (1968) Таблицы индексов и примитивных корней , Математические таблицы Королевского общества, том 9, Cambridge University Press.
- ^ М. Kraitchik, Théorie де nombres , Готье - Villards, 1922
- ^ Pohlig, S. Алгебраические и комбинаторные аспекты криптографии . Tech. Rep. No. 6602-1, Stanford Electron. Labs., Стэнфорд, Калифорния, октябрь 1977 г.
- ^ ME Hellman и JM Reyneri, Быстрое вычисление дискретных логарифмов в GF (q), Достижения в криптологии - Proceedings of Crypto, 1983
- ^ Л. Адлеман, Субэкспоненциальный алгоритм для задачи дискретного логарифмирования с приложениями к криптографии , В 20-м ежегодном симпозиуме по основам информатики, 1979 г.
- ^ A. Joux, Новый алгоритм исчисления индекса со сложностью в очень малой характеристике [1]