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

Алгоритм Шуфа — эффективный алгоритм подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой.

Алгоритм опубликовал в 1985 Рене Шуф и это был теоретический прорыв, поскольку это был первый детерминированный алгоритм полиномиального времени для подсчёта точек на эллиптической кривой. До алгоритма Шуфа подходы к подсчёту точек на эллиптических кривых, каким был бесхитростный алгоритм малых и больших шагов, были по большей части трудоёмкими и требовали экспоненционального времени работы.

Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма.

Введение

Пусть $E$ — эллиптическая кривая, определённая над конечным полем ${\mathbb{𝔽}}_q$, где $q=p^n$ для простого $p$ и целого $n\ge 1$. Над полем с характеристикой $\ne 2,3$ эллиптическая кривая может быть задана (коротко) уравнением Вейерштрасса

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

с $A,B\in {\mathbb{𝔽}}_q$. Множество точек, определённых над ${\mathbb{𝔽}}_q$, состоит из решений $(a,b)\in {\mathbb{𝔽}}_q^2$, удовлетворяющих уравнению кривой, и бесконечно удалённой точки $O$. Если использовать групповой закон на эллиптических кривых на этом множестве, можно видеть, что это множество $E({\mathbb{𝔽}}_q)$ образует абелеву группу, в которой $O$ действует как нулевой элемент. Чтобы посчитать точки на эллиптической кривой, мы подсчитываем мощность множества $E({\mathbb{𝔽}}_q)$. В подходе Шуфа для подсчёта мощности $\mathrm{♯}E({\mathbb{𝔽}}_q)$ используется теорема Хассе об эллиптических кривых вместе с китайской теоремой об остатках и многочленами деления.

Теорема Хассе

Основная статья: Теорема Хассе

Теорема Хассе утверждает, что если $E/{\mathbb{𝔽}}_q$ является эллиптической кривой над конечным полем ${\mathbb{𝔽}}_q$, то $\mathrm{♯}E({\mathbb{𝔽}}_q)$ удовлетворяет неравенству

$\mid q+1-\mathrm{♯}E({\mathbb{𝔽}}_q)\mid \le 2\sqrt{q}.$

Этот сильный результат, полученный Хассе в 1934, упрощает нашу задачу путём сужения $\mathrm{♯}E({\mathbb{𝔽}}_q)$ к конечному (хотя и большому) множеству возможностей. Если определить $t$ как $q+1-\mathrm{♯}E({\mathbb{𝔽}}_q)$ и использовать этот результат, мы получим, что вычисление мощности $t$ по модулю $N$, где $N>4\sqrt{q}$, достаточно для вычисления $t$, а потому и для получения $\mathrm{♯}E({\mathbb{𝔽}}_q)$. Хотя нет эффективного пути вычисления $t(\mathrm{mod}N)$ прямо для чисел $N$ общего вида, можно вычислить $t(\mathrm{mod}l)$ для малого простого числа $l$ довольно эффективно. Мы выбираем $S=\{l_1,l_2,...,l_r\}$ в качестве множества различных простых чисел, таких, что $\prod l_i=N>4\sqrt{q}$. Если задано $t(\mathrm{mod}{l}_i)$ для всех $l_i\in S$, китайская теорема об остатках позволяет вычислить $t(\mathrm{mod}N)$.

Чтобы вычислить $t(\mathrm{mod}l)$ для простого $l\ne p$, мы используем теорию эндоморфизма Фробениуса $\varphi$ и многочлены деления. Заметим, что рассмотрение простых чисел $l\ne p$ не приводит к проблемам, поскольку мы всегда можем выбрать большее простое число, чтобы обеспечить, чтобы произведение было достаточно велико. В любом случае алгоритм Шуфа наиболее часто используется для случая $q=p$, поскольку имеются более эффективные, так называемые $p$-адичные алгоритмы, для полей с малой характеристикой.

Эндоморфизм Фробениуса

Если задана эллиптическая кривая $E$, определённая над ${\mathbb{𝔽}}_q$, мы рассматриваем точки на $E$ над ${\overline{\mathbb{𝔽}}}_q$, алгебраическим замыканием поля ${\mathbb{𝔽}}_q$. То есть мы разрешаем точкам иметь координаты в ${\overline{\mathbb{𝔽}}}_q$. Эндоморфизм Фробениуса ${\overline{\mathbb{𝔽}}}_q$ над ${\mathbb{𝔽}}_q$ расширяет эллиптическую кривую отображением $\varphi :(x,y)\mapsto (x^q,y^q)$.

Это отображение тождественно на $E({\mathbb{𝔽}}_q)$ и можно расширить его точкой на бесконечности $O$, что делает его морфизмом группы из$E(\overline{{\mathbb{𝔽}}_q})$ на себя.

Эндоморфизм Фробениуса удовлетворяет квадратному уравнению, связанному с мощностью $E({\mathbb{𝔽}}_q)$ по следующей теореме:

Теорема: Эндоморфизм Фробениуса, заданный отображением $\varphi$, удовлетворяет характеристическому уравнению

${\varphi }^2-t\varphi +q=0$, где $t=q+1-\mathrm{♯}E({\mathbb{𝔽}}_q)$

Тогда для всех $P=(x,y)\in E$ имеем $(x^{q^2},y^{q^2})+q(x,y)=t(x^q,y^q)$, где + означает сложение эллиптической кривой, а $q(x,y)$ и $t(x^q,y^q)$ означают скалярное произведение точки $(x,y)$ на $q$ и точки $(x^q,y^q)$ на $t$.

Можно попытаться в символьном виде вычислить эти точки $(x^{q^2},y^{q^2})$, $(x^q,y^q)$ и $q(x,y)$ как функции на координатном кольце ${\mathbb{𝔽}}_q[x,y]/(y^2-x^3-Ax-B)$ на кривой $E$, а затем искать значение $t$, которое удовлетворяет уравнению. Однако степени получаются очень большими и такой подход практического значения не имеет.

Идея Шуфа заключалась в выполнении таких вычислений, ограничиваясь точками порядка $l$ для различных малых простых чисел $l$. Фиксируя нечётное простое число $l$ мы переходим к решению задачи определения $t_l$, определённого как $t(\mathrm{mod}l)$, для заданного простого $l\ne 2,p$. Если точка $(x,y)$ находится в подгруппе $l$-кручения $E[l]=\{P\in E(\overline{{\mathbb{𝔽}}_q})\mid lP=O\}$, то $qP=\overline{q}P$, где $\overline{q}$ является единственным целым числом, таким, что $q\equiv \overline{q}(\mathrm{mod}l)$ и $\mid \overline{q}\mid <l/2$. Заметим, что $\varphi (O)=O$ и что для любого целого $r$ мы имеем $r\varphi (P)=\varphi (rP)$. Таким образом, $\varphi (P)$ имеет тот же порядок, что и $P$. Тогда для $(x,y)$, принадлежащего $E[l]$, мы имеем также $t(x^q,y^q)=\overline{t}(x^q,y^q)$, если $t\equiv \overline{t}(\mathrm{mod}l)$. Следовательно, мы свели нашу задачу к решению уравнения

$(x^{q^2},y^{q^2})+\overline{q}(x,y)\equiv \overline{t}(x^q,y^q),$

где $\overline{t}$ и $\overline{q}$ лежат в интервале $[-(l-1)/2,(l-1)/2]$.

Вычисления по простому модулю

Многочлен деления с номером l — это такой многочлен, что его корни являются в точности x координатами точек порядка l. Тогда ограничение вычисления $(x^{q^2},y^{q^2})+\overline{q}(x,y)$ на точки l-кручения означает вычисление этих выражений как функций координатного кольца E и модуля l-го многочлена деления. То есть мы работаем в ${\mathbb{𝔽}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l)$. Это, в частности, означает, что степень X и Y, определяемых через $(X(x,y),Y(x,y)):=(x^{q^2},y^{q^2})+\overline{q}(x,y)$ не превышают 1 по переменной y и $(l^2-3)/2$ по переменной x.

Скалярное произведение $\overline{q}(x,y)$ может быть осуществлено методом удвоить-и-сложить, либо с помощью $\overline{q}$-го многочлена деления. Второй подход даёт:

$\overline{q}(x,y)=(x_{\overline{q}},y_{\overline{q}})=(x-\frac{{\psi }_{\overline{q}-1}{\psi }_{\overline{q}+1}}{{\psi }_{\overline{q}}^2},\frac{{\psi }_{2\overline{q}}}{2{\psi }_{\overline{q}}^4})$,

где ${\psi }_n$ — n-й многочлен деления. Заметим, что $y_{\overline{q}}/y$ является функцией только от x, обозначим эту функцию через $\theta (x)$.

Мы должны разбить задачу на два случая: случай, в котором $(x^{q^2},y^{q^2})\ne \pm \overline{q}(x,y)$, и случай, в котором $(x^{q^2},y^{q^2})=\pm \overline{q}(x,y)$.

Случай 1: $(x^{q^2},y^{q^2})\ne \pm \overline{q}(x,y)$

Используя формулу сложения для группы $E({\mathbb{𝔽}}_q)$, мы получим:

$X(x,y)={\left(\frac{y^{q^2}-y_{\overline{q}}}{x^{q^2}-x_{\overline{q}}}\right)}^2-x^{q^2}-x_{\overline{q}}.$

Заметим, что это вычисление невозможно, если предположение о неравенстве не выполняется.

Мы теперь можем сузить выбор координаты x для $\overline{t}$ до двух возможностей, а именно — положительного и отрицательного случаев. Используя координату y, определяем, который из двух случаев имеет место.

Сначала мы покажем, что X является функцией только от x. Рассмотрим $(y^{q^2}-y_{\overline{q}}{)}^2=y^2(y^{q^2-1}-y_{\overline{q}}/y{)}^2$. Поскольку $q^2-1$ чётно, заменив $y^2$ на $x^3+Ax+B$, мы переписываем выражение как

$(x^3+Ax+B)((x^3+Ax+B{)}^{\frac{q^2-1}{2}}-\theta (x))$

и имеем

$X(x)\equiv (x^3+Ax+B)((x^3+Ax+B{)}^{\frac{q^2-1}{2}}-\theta (x)){mod\psi }_l(x).$

Теперь, если $X\equiv x_{\overline{t}}^q{mod\psi }_l(x)$ для $\overline{t}\in [0,(l-1)/2]$, то для $\overline{t}$ верно равенство

${\varphi }^2(P)\mp \overline{t}\varphi (P)+\overline{q}P=O$

для всех точек P l-кручения.

Как было упомянуто ранее, используя Y и $y_{\overline{t}}^q$, мы можем теперь определить, какое из двух значений $\overline{t}$ ($\overline{t}$ или $-\overline{t}$) работает. Это даёт значение $t\equiv \overline{t}(\mathrm{mod}l)$. Алгоритм Шуфа запоминает значения $\overline{t}(\mathrm{mod}l)$ в переменной $t_l$ для каждого рассматриваемого простого l.

Случай 2: $(x^{q^2},y^{q^2})=\pm \overline{q}(x,y)$

Предположим, что $(x^{q^2},y^{q^2})=\overline{q}(x,y)$. Поскольку l является нечётным простым числом, невозможно, чтобы $\overline{q}(x,y)=-\overline{q}(x,y)$, а следовательно, $\overline{t}\ne 0$. Из характеристического уравнения следует, что $\overline{t}\varphi (P)=2\overline{q}P$, а следовательно, что ${\overline{t}}^2\overline{q}\equiv (2q{)}^2(\mathrm{mod}l)$. Из этого следует, что q является квадратом по модулю l. Пусть $q\equiv w^2(\mathrm{mod}l)$. Вычислим $w\varphi (x,y)$ в ${\mathbb{𝔽}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l)$ и проверим, выполняется ли $\overline{q}(x,y)=w\varphi (x,y)$. Если так, то $t_l$ является $\pm 2w(\mathrm{mod}l)$, в зависимости от координаты y.

Если q окажется не равным квадрату по модулю l или если равенство не выполняется для некоторого w и $-w$, наше предположение, что $(x^{q^2},y^{q^2})=+\overline{q}(x,y)$ неверно, так что $(x^{q^2},y^{q^2})=-\overline{q}(x,y)$. Характеристическое уравнение даёт $t_l=0$.

Дополнительный случай $l=2$

Если вспомнить, наши начальные соглашения не рассматривают случая $l=2$. Поскольку мы предположили, что q нечётно, $q+1-t\equiv t(\mathrm{mod}2)$ и, в частности, $t_2\equiv 0(\mathrm{mod}2)$ тогда и только тогда, когда $E({\mathbb{𝔽}}_q)$ имеет элемент порядка 2. По определению сложения в группе любой элемент порядка 2 должен иметь вид $(x_0,0)$. Таким образом $t_2\equiv 0(\mathrm{mod}2)$ тогда и только тогда, когда многочлен $x^3+Ax+B$ имеет корень в ${\mathbb{𝔽}}_q$, тогда и только тогда, когда НОД$(x^q-x,x^3+Ax+B)\ne 1$.

Алгоритм

    Ввод:
        1. Эллиптическая кривая $E=y^2-x^3-Ax-B$.
        2. Целое число q для конечного поля $F_q$ с $q=p^b,b\ge 1$.
    Вывод:
        Число точек E над $F_q$.
    Выбираем множество нечётных простых чисел S, не содержащее p, такое, что  $N=\prod _{l\in S}l>4\sqrt{q}.$
    Примем $t_2=0$, если НОД$(x^q-x,x^3+Ax+B)\ne 1$, иначе принимаем $t_2=1$.
    Вычисляем многочлен деления ${\psi }_l$. 
    Все вычисления в цикле ниже осуществляются в кольце ${\mathbb{𝔽}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l).$
    Для $l\in S$ выполняем:
        Пусть $\overline{q}$ — единственное целое  такое, что $q\equiv \overline{q}(\mathrm{mod}l)$ и $\mid \overline{q}\mid <l/2$.
        Вычисляем $(x^q,y^q)$, $(x^{q^2},y^{q^2})$ и $(x_{\overline{q}},y_{\overline{q}})$.   
        Если $x^{q^2}\ne x_{\overline{q}}$  то
            Вычисляем $(X,Y)$.
            для $1\le \overline{t}\le (l-1)/2$ выполняем:
                если $X=x_{\overline{t}}^q$ то
                    если $Y=y_{\overline{t}}^q$ то
                        $t_l=\overline{t}$;
                    иначе
                        $t_l=-\overline{t}$.
        иначе если q является квадратом по модулю l  то 
            вычисляем w с $q\equiv w^2(\mathrm{mod}l)$
             вычисляем $w(x^q,y^q)$
            если $w(x^q,y^q)=(x^{q^2},y^{q^2})$  то
                $t_l=2w$
            иначе если $w(x^q,y^q)=(x^{q^2},-y^{q^2})$ то
                $t_l=-2w$
            иначе
                $t_l=0$
        иначе
            $t_l=0$
    Используем китайскую теорему об остатках для вычисления t по модулю N из уравнения $x\equiv t_l(\mathrm{mod}l)$, где $l\in S$.
    Выводим $q+1-t$.

Сложность

Большинство вычислений заключаются в вычислении $\varphi (P)$ и ${\varphi }^2(P)$, для каждого простого числа $l$, то есть вычислении $x^q$, $y^q$, $x^{q^2}$, $y^{q^2}$ для каждого простого числа $l$. Вычисления включают возведение в степень в кольце $R={\mathbb{𝔽}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l)$ и требуют $O(\log q)$ умножений. Поскольку степень ${\psi }_l$ равна $\frac{l^2-1}{2}$, каждый элемент в кольце является многочленом степени $O(l^2)$. По теореме о распределении простых чисел имеется около $O(\log q)$ простых чисел размера $O(\log q)$, что даёт для $l$ значение $O(\log q)$, и мы получаем $O(l^2)=O({\log }^{2}q)$. Таким образом, каждое умножение в кольце $R$ требует $O({\log }^{4}q)$ умножений в ${\mathbb{𝔽}}_q$, что, в свою очередь, требует, $O({\log }^{2}q)$ битовых операций. В общей сложности число битовых операций для каждого простого числа $l$ равно $O({\log }^{7}q)$. Если принять, что это вычисление требуется провести для каждого из $O(\log q)$ простых чисел, полная сложность алгоритма Шуфа становится $O({\log }^{8}q)$. Использование быстрых операций с многочленами и целочисленной арифметики сокращает это время до $\tilde{O}({\log }^{5}q)$.

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

Основная статья: Алгоритм Шуфа — Элкиса — Аткина

В 1990-х годах Ноам Элкис, а затем А. О. Л. Аткин придумали улучшения базового алгоритма Шуфа путём ограничения множества простых чисел $S=\{l_1,\dots ,l_s\}$ до чисел определённого вида. Эти числа стали называться простыми Элкиса и простыми Аткина соответственно. Простое число $l$ называется простым Элкиса, если характеристическое равенство ${\varphi }^2-t\varphi +q=0$ разложим над ${\mathbb{𝔽}}_l$, а простые Аткина — это простые, не являющиеся простыми Элкиса. Аткин показал как комбинировать информацию, полученную из простых Аткина, с информацией, полученной из простых Элкиса, чтобы получить эффективный алгоритм, который получил название «Алгоритм Шуфа — Элкиса — Аткина». Первая задача — определить, данное простое является простым Элкиса, или Аткина. Чтобы это получить, используем модулярные многочлены, которые возникают при изучении модулярных форм и интерпретации эллиптических кривых над полем комплексных чисел как решёток. Как только мы определим, какой случай мы имеем, вместо использования многочленов деления мы можем работать с многочленами, имеющими меньшие степени по сравнению с многочленами деления: $O(l)$ вместо $O(l^2)$. Для эффективной имплементации используются вероятностные алгоритмы поиска корней, что делает алгоритм алгоритмом Лас-Вегаса, а не детерминированным алгоритмом. При эвристическом предположении, что примерно половина простых чисел, не превосходящих $O(\log q)$, являются простыми Элкиса, это даёт алгоритм, который эффективнее алгоритма Шуфа, и ожидаемое время работы этого алгоритма равно $O({\log }^{6}q)$, если использовать обычную арифметику, и $\tilde{O}({\log }^{4}q)$, если использовать быструю арифметику. Следует заметить, что это эвристическое предположение верно для большинства эллиптических кривых, но не известно для общего случая, даже при верности обобщённой гипотезы Римана.

Имплементации

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

• Алгоритм Шуфа с имплементацией для $E({\mathbb{𝔽}}_p)$ с простым $p$.
• Алгоритм Шуфа с имплементацией для $E({\mathbb{𝔽}}_{2^m})$.

См. также

• Эллиптическая криптография
• Подсчёт точек на эллиптической кривой
• многочлены деления
• Эндоморфизм Фробениуса