Введение

Алгоритм Шуфа — эффективный алгоритм для подсчёта точек на эллиптических кривых над конечными полями. Этот алгоритм находит применение в криптографии на эллиптических кривых, где знание количества точек важно для оценки сложности задачи дискретного логарифмирования в группе точек эллиптической кривой. Алгоритм был опубликован Рене Шуфом в 1985 году и стал теоретическим прорывом, поскольку он был первым детерминированным алгоритмом полиномиального времени для подсчёта точек на эллиптических кривых. До появления алгоритма Шуфа подходы к подсчёту точек на эллиптических кривых, такие как наивный и алгоритм «шаг младенца — гигантский шаг», в основном были трудоёмкими и имели экспоненциальное время работы. В данной статье объясняется подход Шуфа с акцентом на математические идеи, лежащие в основе структуры алгоритма.

Введение

Пусть E — эллиптическая кривая, определенная над конечным полем F_q, где q = p^n для простого числа p и целого n. Над полем характеристики p эллиптическая кривая может быть задана (коротким) уравнением Вейерштрасса

с условием, что дискриминант не равен нулю. Множество точек, определенных над F_q, состоит из решений (x, y), удовлетворяющих уравнению кривой, и точки на бесконечности. Используя групповой закон на эллиптических кривых, ограниченный этим множеством, можно увидеть, что это множество образует абелеву группу, с точкой на бесконечности, действующей как нулевой элемент. Для подсчета точек на эллиптической кривой мы вычисляем ее кардинальность. Подход Шуфа к вычислению кардинальности использует теорему Хассе об эллиптических кривых вместе с китайской теоремой об остатках и многочленами деления.

Вычисление модульных простых чисел

Полином деления на l-е место таков, что его корни – это как раз x-координаты точек порядка l. Таким образом, ограничение вычислений точками кручения l-го порядка означает вычисление этих выражений как функций в координатном кольце E и по модулю l-го полинома деления. То есть мы работаем в . Это означает, в частности, что степень X и Y, определенных через , не превышает 1 по y и не превышает 1 по x. Скалярное умножение можно выполнить либо методом удвоения и сложения, либо с помощью полинома деления. Последний подход дает:

где – n-й полином деления. Отметим, что это функция только от x, и обозначим ее как . Мы должны разбить задачу на два случая: случай, когда , и случай, когда . Отметим, что эти равенства проверяются по модулю .

Случай 2:

Мы начинаем с предположения, что поскольку l – нечетное простое число, не может быть так, и, следовательно, характеристическое уравнение дает, что и, как следствие, что. Это подразумевает, что q является квадратом по модулю l. Вычислим в и проверим, является ли . Если да, то зависит от y-координаты. Если q не является квадратом по модулю l или если уравнение не выполняется ни для одного из w и , наше предположение неверно, таким образом, характеристическое уравнение дает.

Дополнительное дело

Если вы помните, наши первоначальные соображения исключают случай, когда . Поскольку мы предполагаем, что q нечетно, то , и в частности, тогда и только тогда, когда имеет элемент порядка 2. По определению сложения в группе, любой элемент порядка 2 должен иметь вид . Таким образом, тогда и только тогда, когда многочлен имеет корень в , тогда и только тогда, когда .

Сложность

Большая часть вычислений приходится на вычисление и для каждого простого числа , то есть вычисление , , , для каждого простого числа . Это включает в себя возведение в степень в кольце и требует умножений. Поскольку степень равна , каждый элемент в кольце является многочленом степени . По теореме о простых числах, существует около простых чисел размера , что дает , и мы получаем, что . Таким образом, каждое умножение в кольце требует умножений в , что, в свою очередь, требует битовых операций. В общей сложности, количество битовых операций для каждого простого числа равно . Учитывая, что это вычисление необходимо выполнить для каждого из простых чисел, общая сложность алгоритма Шуфа оказывается. Использование быстрой полиномиальной и целочисленной арифметики снижает эту сложность до .

Улучшения алгоритма Шуфа

В 1990-х годах Ноам Элкис, а затем А. О. Л. Аткин, разработали улучшения к основному алгоритму Шуфа, ограничив множество рассматриваемых простых чисел простыми числами определенного вида. Эти простые числа стали называться, соответственно, простыми числами Элкиса и простыми числами Аткина. Простое число называется числом Элкиса, если его характеристическое уравнение распадается на множители в , а простое число, не являющееся числом Элкиса, называется числом Аткина. Аткин показал, как комбинировать информацию, полученную из простых чисел Аткина, с информацией, полученной из простых чисел Элкиса, для создания эффективного алгоритма, который стал известен как алгоритм Шуфа–Элкиса–Аткина. Первая задача, которую необходимо решить, — определить, является ли данное простое число числом Элкиса или Аткина. Для этого мы используем модульные полиномы, которые берут начало в изучении модульных форм и интерпретации эллиптических кривых над комплексными числами как решёток. Как только мы определили, какой случай имеет место, вместо использования полиномов деления, мы можем работать с полиномом, степень которого ниже, чем у соответствующего полинома деления: вместо . Для эффективной реализации используются вероятностные алгоритмы поиска корней, что делает этот алгоритм алгоритмом Лас-Вегаса, а не детерминированным алгоритмом. При эвристическом предположении, что примерно половина простых чисел до границы являются простыми числами Элкиса, получается алгоритм, более эффективный, чем алгоритм Шуфа, со средним временем работы, использующим наивную арифметику, и, использующим быструю арифметику. Хотя известно, что это эвристическое предположение выполняется для большинства эллиптических кривых, неизвестно, выполняется ли оно в каждом случае, даже при условии GRH.

Реализация

Несколько алгоритмов были реализованы на C++ Майком Скоттом и доступны с исходным кодом. Реализации бесплатны (без каких-либо условий) и используют библиотеку MIRACL, распространяемую под лицензией AGPLv3. Реализация алгоритма Шуфа для с простым и реализация алгоритма Шуфа для .