Алгоритм индексного исчисления для вычисления дискретных логарифмов

Введение

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

Описание

Грубо говоря, задача о дискретном логарифме ставит перед нами задачу найти такое x, что , где g, h и модуль n заданы. Алгоритм (подробно описан ниже) применим к группе , где q – простое число. Для его работы требуется факторная база в качестве входных данных. Обычно эта факторная база выбирается как число −1 и первые r простых чисел, начиная с 2. С точки зрения эффективности, нам нужна небольшая факторная база, но для решения задачи дискретного логарифма для большой группы требуется, чтобы факторная база была (относительно) большой. В практических реализациях алгоритма эти противоречивые цели так или иначе компромиссны. Алгоритм выполняется в три этапа. Первые два этапа зависят только от генератора g и простого модуля q и находят дискретные логарифмы r малых простых чисел, входящих в факторную базу. Третий этап находит дискретный логарифм искомого числа h относительно дискретных логарифмов элементов факторной базы. Первый этап состоит в поиске набора из r линейно независимых соотношений между факторной базой и степенями генератора g. Каждое соотношение дает одно уравнение в системе линейных уравнений с r неизвестными, а именно дискретными логарифмами r простых чисел в факторной базе. Этот этап легко распараллеливается и может быть легко распределен между многими компьютерами. На втором этапе решается система линейных уравнений для вычисления дискретных логарифмов элементов факторной базы. Система, состоящая из сотен тысяч или миллионов уравнений, требует значительных вычислительных ресурсов и большого объема памяти, и она не обладает свойством легкой распараллеливаемости, поэтому обычно используется суперкомпьютер. Для небольших вычислений дискретных логарифмов это считалось незначительным шагом. Однако новые рекорды в вычислении дискретных логарифмов стали возможны только благодаря переносу вычислительной нагрузки с линейной алгебры на решето (то есть увеличению числа уравнений при уменьшении числа переменных). На третьем этапе ищется степень s генератора g, которая, будучи умноженной на аргумент h, может быть разложена на множители, принадлежащие факторной базе: gsh = (−1)f0 2f1 3f2···prfr. Наконец, в операции, слишком простой, чтобы ее можно было назвать четвертым этапом, результаты второго и третьего этапов могут быть перекомбинированы с помощью простых алгебраических преобразований для получения искомого дискретного логарифма: x = f0logg(−1) + f1logg2 + f2logg3 + ··· + frloggpr − s.

Roughly speaking, the discrete log problem asks us to find an x such that , where g, h, and the modulus n are given. The algorithm (described in detail below) applies to the group where q is prime. It requires a factor base as input. This factor base is usually chosen to be the number −1 and the first r primes starting with 2. From the point of view of efficiency, we want this factor base to be small, but in order to solve the discrete log for a large group we require the factor base to be (relatively) large. In practical implementations of the algorithm, those conflicting objectives are compromised one way or another. The algorithm is performed in three stages. The first two stages depend only on the generator g and prime modulus q, and find the discrete logarithms of a factor base of r small primes. The third stage finds the discrete log of the desired number h in terms of the discrete logs of the factor base. The first stage consists of searching for a set of r linearly independent relations between the factor base and power of the generator g. Each relation contributes one equation to a system of linear equations in r unknowns, namely the discrete logarithms of the r primes in the factor base. This stage is embarrassingly parallel and easy to divide among many computers. The second stage solves the system of linear equations to compute the discrete logs of the factor base. A system of hundreds of thousands or millions of equations is a significant computation requiring large amounts of memory, and it is not embarrassingly parallel, so a supercomputer is typically used. This was considered a minor step compared to the others for smaller discrete log computations. However, larger discrete logarithm records were made possible only by shifting the work away from the linear algebra and onto the sieve (i. e., increasing the number of equations while reducing the number of variables). The third stage searches for a power s of the generator g which, when multiplied by the argument h, may be factored in terms of the factor base gsh = (−1)f0 2f1 3f2···prfr. Finally, in an operation too simple to really be called a fourth stage, the results of the second and third stages can be rearranged by simple algebraic manipulation to work out the desired discrete logarithm x = f0logg(−1) + f1logg2 + f2logg3 + ··· + frloggpr − s.

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

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

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

История

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

Семейство Index Calculus

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