Подсчёт точек на эллиптических кривых

Подсчёт точек на эллиптических кривых — группа методов, которые позволяют эффективно вычислять точки на эллиптических кривых. Подсчёт точек на эллиптических кривых используется при изучении теории чисел, криптографии и создании цифровых подписей (см. Эллиптическая криптография и ECDSA). Уровень безопасности криптосистемы, построенной на эллиптической кривой $E({𝔽}_q)$ над конечным полем ${𝔽}_q$, где q = p^k, а p — простое число, определяется сложностью задачи дискретного логарифмирования (DLP) для данной эллиптической кривой $E({𝔽}_q)$. Ниже будут рассмотрены алгоритмы подсчёта точек на эллиптических кривых над полями больших характеристик, в частности, p > 3. Для кривых над полями небольших характеристик существуют более эффективные алгоритмы, основанные на p-адических методах.

Подходы к подсчёту точек на эллиптических кривых

Основными подходами являются простейший метод подсчёта точек на эллиптических кривых, алгоритм больших и малых шагов, подход, предложенный Шаблон:Не переведено 5, и улучшения алгоритма Шуфа, предложенные Н. Элкисом и Шаблон:Не переведено 5.

Некоторые алгоритмы используют тот факт, что к группам вида $E({𝔽}_q)$ применима теорема Хассе, которая гласит, что если E является эллиптической кривой над конечным полем ${𝔽}_q$, то мощность $E({𝔽}_q)$ удовлетворяет неравенству

$||E({𝔽}_q)|-(q+1)|\le 2\sqrt{q}.$

Простейший подход

Простейший подход к подсчёту точек предполагает перебор всех элементов поля ${𝔽}_q$ и проверку того, какие из них удовлетворяют уравнению Вейерштрасса эллиптической кривой

$y^2=x^3+Ax+B.$

Пример

Пусть E будет кривой y² = x³ + x + 1 над полем ${𝔽}_5$. Для подсчёта точек на E строится таблица из возможных значений x, квадратичных вычетов x mod 5 (только для поиска), x³ + x + 1 mod 5 и y (по x² и x³ + x + 1 mod 5).

$x$	$x^2$	$x^3+x+1$	$y$	Points
$0$	$0$	$1$	$1,4$	$(0,1),(0,4)$
$1$	$1$	$3$	$-$	$-$
$2$	$4$	$1$	$1,4$	$(2,1),(2,4)$
$3$	$4$	$1$	$1,4$	$(3,1),(3,4)$
$4$	$1$	$4$	$2,3$	$(4,2),(4,3)$

Последняя строка вычисляется следующим образом: в уравнение $y^2=x^3+x+1$ подставляется $x=4$, что приводит к $y^2=4$ (3-й столбец). Такой же результат получается при $y=2,3$ (Квадратичные вычеты находятся во втором столбце). Так, для последней строки находятся точки $(4,2),(4,3)$.

Таким образом, $E({𝔽}_5)$ имеет порядок 9: 8 вычисленных точек и точка на бесконечности.

Вычислительная сложность алгоритма O(q), поскольку должны быть рассмотрены все значения $x\in {𝔽}_q$.

Алгоритм больших и маленьких шагов

Снижение вычислительной сложности алгоритма было получено путём применения другого подхода: перебором случайных значений $x$, пока $x^3+Ax+B$ не будет квадратом на ${𝔽}_q$, выбирается элемент $P=(x,y)\in E({𝔽}_q)$ такой, что $y$ является квадратным корнем из $x^3+Ax+B$. Теорема Хассе гласит, что $|E({𝔽}_q)|$ принадлежит интервалу $(q+1-2\sqrt{q},q+1+2\sqrt{q})$. Тогда по теореме Лагранжа задача нахождения мощности множества $E({𝔽}_q)$ сводится к поиску уникального $M$, принадлежащего этому интервалу и удовлетворяющего равенству $MP=O$. Алгоритм перестаёт работать, если существуют два таких $M$ и $M^{\prime }$, принадлежащих интервалу и удовлетворяющих равенству $MP=M^{\prime }P=O$. В таком случае достаточно повторить ход алгоритма с другим случайно подобранным $P=(x,y)\in E({𝔽}_q)$.

Перебор всех значений $M$ с целью найти единственное, удовлетворяющее равенству $MP=O$, занимает около $4\sqrt{q}$ шагов.

Однако, применяя алгоритм больших и маленьких шагов к $E({𝔽}_q)$, можно ускорить поиск до $4\sqrt[4]{q}$ шагов.

Алгоритм

1. choose $m$ integer, $m>\sqrt[4]{q}$
2. FOR{$j=0$ to $m$} DO 
3.    $P_j\leftarrow jP$
4. ENDFOR
5. $L\leftarrow 1$
6. $Q\leftarrow (q+1)P$
7. REPEAT compute the points $Q+k(2mP)$
8. UNTIL $\mathrm{\exists }j$: $Q+k(2mP)=\pm P_j$  \\the $x$-coordinates are compared
9. $M\leftarrow q+1+2mk\mp j$     \\note $MP=O$
10. Factor $M$. Let $p_1,\dots ,p_r$ be the distinct prime factors of $M$.
11. WHILE $i\le r$ DO
12.    IF $\frac{M}{p_i}P=O$
13.       THEN $M\leftarrow \frac{M}{p_i}$
14.       ELSE $i\leftarrow i+1$ 
15.    ENDIF
16. ENDWHILE
17. $L\leftarrow \mathrm{lcm}(L,M)$     \\note $M$ is the order of the point $P$
18. WHILE $L$ divides more than one integer $N$ in $(q+1-2\sqrt{q},q+1+2\sqrt{q})$
19.    DO choose a new point $P$ and go to 1.
20. ENDWHILE
21. RETURN $N$     \\it is the cardinality of $E({𝔽}_q)$

Пояснения к алгоритму

• в пункте 8. допускается существование такого совпадения. Следующая лемма гарантирует, что такое совпадение существует:

Пусть $a$ — целое, $|a|\le 2m^2$. Существуют $a_0$ и $a_1$ такие, что

$-m<a_0\le m\text{ и }-m\le a_1\le m\text{ т.ч. }a=a_0+2m{a}_1.$

• Как только было подсчитано $jP$, для вычисления $(j+1)P$ достаточно прибавить $P$ к $jP$ вместо того, чтобы производить суммирование по всем $j+1$ элементам. Таким образом, полный цикл вычислений требует $m$ сложений. $2mP$ может быть получено удвоением $mP$. Вычисление $Q$ требует $\log (q+1)$ удвоений и $w$ сложений, где $w$ число ненулевых элементов в бинарном представлении $q+1$; следует отметить, что знание $jP$ и $2mP$ позволяет уменьшить число операций удвоения. Наконец, чтобы из $Q+k(2mP)$ получить $Q+(k+1)(2mP)$, нужно просто прибавить $2mP$ вместо того, чтобы производить суммирование с начала.
• Предполагается, что можно факторизовать $M$. Если нет, то по крайней мере можно найти все маленькие простые факторы $p_i$ и проверить, что для них $\frac{M}{p_i}\ne O$. Так, $M$ является хорошим кандидатом в порядок $P$.
• Заключение шага 17 может быть доказано с использованием элементарной теории групп: поскольку $MP=O$, порядок $P$ делится на $M$ без остатка. Если нет подходящего делителя $\overline{M}$ числа $M$, для которого $\overline{M}P=O$, то $M$ — порядок $P$.

Одним из недостатков этого метода является то, что он требует много памяти, когда группа становится большой. В случае больших групп может быть эффективнее хранить только координаты $x$ точек $jP$ (вместе с соответствующим $j$). Однако это приводит к дополнительным операциям умножения в случае выбора между $-j$ и $+j$.

Существуют и другие алгоритмы вычисления порядка элемента группы, которые будут требовать меньше памяти, такие как ро-алгоритм Полларда и алгоритм «кенгуру» Полларда. Алгоритм «кенгуру» Полларда позволяет найти решение в предписанном интервале, снижая число шагов до $O(\sqrt[4]{q})$ и занимая $O({\log }^{2}q)$ места в памяти.

Алгоритм Шуфа

Теоретический прорыв в области вычисления порядка групп типа $E({𝔽}_q)$ был достигнут Шаблон:Не переведено 5, который в 1985 году опубликовал первый детерминированный полиномиальный алгоритм. В основе алгоритма лежат теорема Хассе об эллиптических кривых вместе с китайской теоремой об остатках и Шаблон:Не переведено 5.

Шуф использует тот факт, что согласно теореме Хассе существует конечное число возможных значений $|E({𝔽}_q)|$. Таким образом, становится достаточным вычислить $|E({𝔽}_q)|$ по модулю целого $N>4\sqrt{q}$. Это можно сделать, вычисляя $|E({𝔽}_q)|$ по модулю простых ${\ell }_1,\dots ,{\ell }_s$, произведение которых превосходит $4\sqrt{q}$, и затем применить китайскую теорему об остатках. Важной составляющей алгоритма является использование многочленов деления ${\psi }_{\ell }$ для эффективного вычисления $|E({𝔽}_q)|$ по модулю $\ell$.

Временная сложность алгоритма Шуфа $n=\log q$, тогда как асимптотическая сложность $O(n^{2}M(n^3)/\log n)=O(n^{5+o(1)})$, где $M(n)$ означает вычислительную сложность целочисленного умножения. Пространственная сложность алгоритма $O(n^3)$.

Алгоритм Шуфа — Элкиса — Аткина

В 1990-х годах Ноам Элкис, а затем Шаблон:Не переведено 5 придумали улучшения базового алгоритма Шуфа путём разделения множества рассматриваемых простых чисел $S=\{l_1,\dots ,l_s\}$. Простое число $\ell$ называется простым Элкиса, если характеристическое уравнение эндоморфизма Фробениуса ${\varphi }^2-t\varphi +q=0$ разложимо над ${𝔽}_{\ell }$. Иначе, $\ell$ называется простым Аткина. С помощью простых Элкиса можно понизить асимптотическую сложность алгоритма Шуфа. Информация, полученная из простых Аткина, ведёт к дальнейшим улучшениям алгоритма, и несмотря на малость вносимого ими вклада в снижение асимптотической сложности алгоритма, простые Аткина важны на практике. Модификация алгоритма Шуфа, использующая простые Элкиса и Аткина, называется Шаблон:Не переведено 5.

Вид простого $\ell$ зависит от эллиптической кривой $E({𝔽}_q)$ и может быть определён с использованием Шаблон:Не переведено 5 ${\mathrm{\Psi }}_{\ell }(X,Y)$. Если полином одной переменной ${\mathrm{\Psi }}_{\ell }(X,j(E))$ имеет корень на ${𝔽}_q$, где $j(E)$ означает Шаблон:Не переведено 5 на $E$, тогда $\ell$ — простое Элкиса, а иначе простое Аткина. В случае простого Элкиса дальнейшее вычисление корней модулярного полинома используется для получения правильного фактора многочлена деления ${\psi }_{\ell }$. Степень получаемого фактора $O(\ell )$, тогда как ${\psi }_{\ell }$ имеет степень $O({\ell }^2)$.

Для эффективной имплементации алгоритма Шуфа — Элкиса — Аткина используются вероятностные алгоритмы поиска корней, что делает алгоритм алгоритмом Лас-Вегаса, а не детерминированным алгоритмом. Вычислительная сложность алгоритма определяется стоимостью вычислений модулярных полиномов ${\mathrm{\Psi }}_{\ell }(X,Y)$, но поскольку они не зависят от $E$, то могут быть вычислены однажды и затем использованы снова. При эвристическом предположении о существовании достаточно большого количества малых простых Элкиса и без учёта стоимости вычисления модулярных полиномов асимптотическая сложность алгоритма Шуфа — Элкиса — Аткина $O(n^{2}M(n^2)/\log n)=O(n^{4+o(1)})$, где $n=\log q$. Пространственная сложность $O(n^3\log n)$, но в случае использования вычисленных заранее модулярных полиномов сложность возрастает до $O(n^4)$.

См. также

• Алгоритм Шуфа
• Эллиптическая криптография
• Алгоритм Гельфонда-Шенкса
• Криптосистема с открытым ключом
• Шаблон:Не переведено 5
• Ро-алгоритм Полларда
• Алгоритм «кенгуру» Полларда

Литература

• I. Blake, G. Seroussi, and N. Smart: Elliptic Curves in Cryptography, Cambridge University Press, 1999.
• A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
• G. Musiker: Schoof’s Algorithm for Counting Points on $E({𝔽}_q)$. Available at http://www.math.umn.edu/~musiker/schoof.pdf
• R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219-254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
• L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman \& Hall/CRC, New York, 2003.