Алгоритм опубликовал в 1985
и это был теоретический прорыв, поскольку это был первый детерминированный алгоритм полиномиального времени для
. До алгоритма Шуфа подходы к подсчёту точек на эллиптических кривых, каким был бесхитростный алгоритм
малых и больших шагов
, были по большей части трудоёмкими и требовали экспоненционального времени работы.
Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма.
Содержание
Введение
Пусть
—
эллиптическая кривая
, определённая над конечным полем
, где
для простого
и целого
. Над полем с характеристикой
эллиптическая кривая может быть задана (коротко) уравнением Вейерштрасса
Теорема Хассе утверждает, что если
является эллиптической кривой над конечным полем
, то
удовлетворяет неравенству
Этот сильный результат, полученный Хассе в 1934, упрощает нашу задачу путём сужения
к конечному (хотя и большому) множеству возможностей. Если определить
как
и использовать этот результат, мы получим, что вычисление мощности
по модулю
, где
, достаточно для вычисления
, а потому и для получения
. Хотя нет эффективного пути вычисления
прямо для чисел
общего вида, можно вычислить
для малого простого числа
довольно эффективно. Мы выбираем
в качестве множества различных простых чисел, таких, что
. Если задано
для всех
,
китайская теорема об остатках
позволяет вычислить
.
Чтобы вычислить
для простого
, мы используем теорию эндоморфизма Фробениуса
и
. Заметим, что рассмотрение простых чисел
не приводит к проблемам, поскольку мы всегда можем выбрать большее простое число, чтобы обеспечить, чтобы произведение было достаточно велико. В любом случае алгоритм Шуфа наиболее часто используется для случая
, поскольку имеются более эффективные, так называемые
-адичные алгоритмы, для полей с малой характеристикой.
Эндоморфизм Фробениуса
Если задана эллиптическая кривая
, определённая над
, мы рассматриваем точки на
над
,
поля
. То есть мы разрешаем точкам иметь координаты в
.
Эндоморфизм Фробениуса
над
расширяет эллиптическую кривую отображением
.
Это отображение тождественно на
и можно расширить его точкой на бесконечности
, что делает его
морфизмом группы
из
на себя.
Эндоморфизм Фробениуса удовлетворяет квадратному уравнению, связанному с мощностью
по следующей теореме:
Тогда для всех
имеем
, где + означает сложение эллиптической кривой, а
и
означают скалярное произведение точки
на
и точки
на
.
Можно попытаться в символьном виде вычислить эти точки
,
и
как функции на
на кривой
, а затем искать значение
, которое удовлетворяет уравнению. Однако степени получаются очень большими и такой подход практического значения не имеет.
Идея Шуфа заключалась в выполнении таких вычислений, ограничиваясь точками порядка
для различных малых простых чисел
.
Фиксируя нечётное простое число
мы переходим к решению задачи определения
, определённого как
, для заданного простого
.
Если точка
находится в
подгруппе
-кручения
, то
, где
является единственным целым числом, таким, что
и
.
Заметим, что
и что для любого целого
мы имеем
. Таким образом,
имеет тот же порядок, что и
. Тогда для
, принадлежащего
, мы имеем также
, если
. Следовательно, мы свели нашу задачу к решению уравнения
где
и
лежат в интервале
.
Вычисления по простому модулю
с номером
l
— это такой многочлен, что его корни являются в точности
x
координатами точек порядка
l
. Тогда ограничение вычисления
на точки
l
-кручения означает вычисление этих выражений как функций координатного кольца
E
и
модуля
l
-го многочлена деления. То есть мы работаем в
. Это, в частности, означает, что степень
X
и
Y
, определяемых через
не превышают 1 по переменной
y
и
по переменной
x
.
Скалярное произведение
может быть осуществлено методом
удвоить-и-сложить
, либо с помощью
-го многочлена деления. Второй подход даёт:
,
где
—
n
-й многочлен деления. Заметим, что
является функцией только от
x
, обозначим эту функцию через
.
Мы должны разбить задачу на два случая: случай, в котором
, и случай, в котором
.
Заметим, что это вычисление невозможно, если предположение о неравенстве не выполняется.
Мы теперь можем сузить выбор координаты
x
для
до двух возможностей, а именно — положительного и отрицательного случаев. Используя координату
y
, определяем, который из двух случаев имеет место.
Сначала мы покажем, что
X
является функцией только от
x
. Рассмотрим
.
Поскольку
чётно, заменив
на
, мы переписываем выражение как
и имеем
Теперь, если
для
, то для
верно равенство
для всех точек
P
l
-кручения.
Как было упомянуто ранее, используя
Y
и
, мы можем теперь определить, какое из двух значений
(
или
) работает. Это даёт значение
. Алгоритм Шуфа запоминает значения
в переменной
для каждого рассматриваемого простого
l
.
Случай 2:
Предположим, что
. Поскольку
l
является нечётным простым числом, невозможно, чтобы
, а следовательно,
. Из характеристического уравнения следует, что
, а следовательно, что
.
Из этого следует, что
q
является квадратом по модулю
l
. Пусть
. Вычислим
в
и проверим, выполняется ли
. Если так, то
является
, в зависимости от координаты y.
Если
q
окажется не равным квадрату по модулю
l
или если равенство не выполняется для некоторого
w
и
, наше предположение, что
неверно, так что
. Характеристическое уравнение даёт
.
Дополнительный случай
Если вспомнить, наши начальные соглашения не рассматривают случая
.
Поскольку мы предположили, что
q
нечётно,
и, в частности,
тогда и только тогда, когда
имеет элемент порядка 2. По определению сложения в группе любой элемент порядка 2 должен иметь вид
. Таким образом
тогда и только тогда, когда многочлен
имеет корень в
, тогда и только тогда, когда НОД
.
Алгоритм
Ввод:
1. Эллиптическая кривая .
2. Целое число q для конечного поля с .
Вывод:
Число точек E над .
Выбираем множество нечётных простых чисел S, не содержащее p, такое, что Примем, если НОД, иначе принимаем.Вычисляем многочлен деления .
Все вычисления в цикле ниже осуществляются в кольце Длявыполняем:Пусть — единственное целое такое, что и .Вычисляем , и .Если тоВычисляем .длявыполняем:еслитоеслито;иначе.иначе еслиq является квадратом по модулю l то вычисляем w с вычисляем если тоиначе еслитоиначеиначе
Используем китайскую теорему об остатках для вычисления t по модулю N из уравнения , где .
Выводим .
Сложность
Большинство вычислений заключаются в вычислении
и
, для каждого простого числа
, то есть вычислении
,
,
,
для каждого простого числа
. Вычисления включают возведение в степень в кольце
и требуют
умножений. Поскольку степень
равна
, каждый элемент в кольце является многочленом степени
. По
теореме о распределении простых чисел
имеется около
простых чисел размера
, что даёт для
значение
, и мы получаем
. Таким образом, каждое умножение в кольце
требует
умножений в
, что, в свою очередь, требует,
битовых операций. В общей сложности число битовых операций для каждого простого числа
равно
. Если принять, что это вычисление требуется провести для каждого из
простых чисел, полная сложность алгоритма Шуфа становится
. Использование быстрых операций с многочленами и целочисленной арифметики сокращает это время до
.
Улучшения алгоритма Шуфа
Основная статья:
В 1990-х годах
Ноам Элкис
, а затем
придумали улучшения базового алгоритма Шуфа путём ограничения множества простых чисел
до чисел определённого вида. Эти числа стали называться простыми Элкиса и простыми Аткина соответственно. Простое число
называется простым Элкиса, если характеристическое равенство
разложим над
, а простые Аткина — это простые, не являющиеся простыми Элкиса. Аткин показал как комбинировать информацию, полученную из простых Аткина, с информацией, полученной из простых Элкиса, чтобы получить эффективный алгоритм, который получил название «
». Первая задача — определить, данное простое является простым Элкиса, или Аткина. Чтобы это получить, используем модулярные многочлены, которые возникают при изучении
модулярных форм
и интерпретации
эллиптических кривых над полем комплексных чисел
как решёток. Как только мы определим, какой случай мы имеем, вместо использования
мы можем работать с многочленами, имеющими меньшие степени по сравнению с многочленами деления:
вместо
. Для эффективной имплементации используются вероятностные алгоритмы поиска корней, что делает алгоритм
алгоритмом Лас-Вегаса
, а не детерминированным алгоритмом.
При эвристическом предположении, что примерно половина простых чисел, не превосходящих
, являются простыми Элкиса, это даёт алгоритм, который эффективнее алгоритма Шуфа, и ожидаемое время работы этого алгоритма равно
, если использовать обычную арифметику, и
, если использовать быструю арифметику. Следует заметить, что это эвристическое предположение верно для большинства эллиптических кривых, но не известно для общего случая, даже при верности
обобщённой гипотезы Римана
.
Имплементации
Некоторые алгоритмы были имплементированы на
C++
Майком Скоттом и доступны в
. Имплементация абсолютно свободная (никаких условий, никаких ограничений), но использует библиотеку
, которая распространяется под лицензией
AGPLv3
.
Хотя, в статье
ECDSA
написано следующее: Алгоритм Скоофа является достаточно неэффективным на практике для значений
p
, которые действительно представляют интерес, то есть
p
> 2
160
.
Точку mP, равную m-кратному сложению точки
P
в аддитивной группе точек эллиптической кривой, называют
скалярным произведением точки на число
m
, а сами точки mP —
скалярными кратными точки
(
). В книге Тиборга (
) то же понятие называется скалярным кратным.
Литература
R. Schoof.
// Math. Comp.. — 1985. —
Т. 44
,
вып. 170
. —
С. 483–494
.
R. Schoof.
// J. Theor. Nombres Bordeaux. — 1995. —
Вып. 7
. —
С. 219–254
.
Gregg Musiker.
. — 2005.
V. Müller.
. — Saarbrücken: Universität des Saarlandes, 1991. — (Master's Thesis).
Andreas Enge.
Elliptic Curves and their Applications to Cryptography: An Introduction. — Dordrecht: Kluwer Academic Publishers, 1999.
Lawrence C. Washington.
Elliptic Curves: Number Theory and Cryptography. — New York: Chapman & Hall/CRC, 2003. — Т. 50. — (Discrete Mathematics and its applications). —
ISBN 978-1-4200-7146-7
.
Neal Koblitz.
A Course in Number Theory and Cryptography. — Second edition. — Springer-Verlag, 1994. — Т. 114. — (Graduate Texts in Mathematics). —
ISBN 0-387-94293-9
.
Х. К. А. ван Тилборг.
Основы криптологии. — Москва: «Мир», 2006. —
ISBN 5-03-003639-3
УДК 519.6.