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

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

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

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

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

${\displaystyle y^{2}=x^{3}+Ax+B}$

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

Теорема Хассе утверждает, что если ${\displaystyle E/\mathbb {F} _{q}}$ является эллиптической кривой над конечным полем ${\displaystyle \mathbb {F} _{q}}$, то ${\displaystyle \sharp E(\mathbb {F} _{q})}$ удовлетворяет неравенству

${\displaystyle \mid q+1-\sharp E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q}}.}$

Этот сильный результат, полученный Хассе в 1934, упрощает нашу задачу путём сужения ${\displaystyle \sharp E(\mathbb {F} _{q})}$ к конечному (хотя и большому) множеству возможностей. Если определить ${\displaystyle t}$ как ${\displaystyle q+1-\sharp E(\mathbb {F} _{q})}$ и использовать этот результат, мы получим, что вычисление мощности ${\displaystyle t}$ по модулю ${\displaystyle N}$, где ${\displaystyle N>4{\sqrt {q}}}$, достаточно для вычисления ${\displaystyle t}$, а потому и для получения ${\displaystyle \sharp E(\mathbb {F} _{q})}$. Хотя нет эффективного пути вычисления ${\displaystyle t{\pmod {N}}}$ прямо для чисел ${\displaystyle N}$ общего вида, можно вычислить ${\displaystyle t{\pmod {l}}}$ для малого простого числа ${\displaystyle l}$ довольно эффективно. Мы выбираем ${\displaystyle S=\{l_{1},l_{2},...,l_{r}\}}$ в качестве множества различных простых чисел, таких, что ${\displaystyle \prod l_{i}=N>4{\sqrt {q}}}$. Если задано ${\displaystyle t{\pmod {l_{i}}}}$ для всех ${\displaystyle l_{i}\in S}$, китайская теорема об остатках позволяет вычислить ${\displaystyle t{\pmod {N}}}$.

Чтобы вычислить ${\displaystyle t{\pmod {l}}}$ для простого ${\displaystyle l\neq p}$, мы используем теорию эндоморфизма Фробениуса ${\displaystyle \phi }$ и многочлены деления^[англ.]. Заметим, что рассмотрение простых чисел ${\displaystyle l\neq p}$ не приводит к проблемам, поскольку мы всегда можем выбрать большее простое число, чтобы обеспечить, чтобы произведение было достаточно велико. В любом случае алгоритм Шуфа наиболее часто используется для случая ${\displaystyle q=p}$, поскольку имеются более эффективные, так называемые ${\displaystyle p}$-адичные алгоритмы, для полей с малой характеристикой.

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

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

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

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

${\displaystyle \phi ^{2}-t\phi +q=0}$, где ${\displaystyle t=q+1-\sharp E(\mathbb {F} _{q})}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и имеем

${\displaystyle X(x)\equiv (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x)){\bmod {\psi }}_{l}(x).}$

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

${\displaystyle \phi ^{2}(P)\mp {\bar {t}}\phi (P)+{\bar {q}}P=O}$

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

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

Предположим, что ${\displaystyle (x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)}$. Поскольку l является нечётным простым числом, невозможно, чтобы ${\displaystyle {\bar {q}}(x,y)=-{\bar {q}}(x,y)}$, а следовательно, ${\displaystyle {\bar {t}}\neq 0}$. Из характеристического уравнения следует, что ${\displaystyle {\bar {t}}\phi (P)=2{\bar {q}}P}$, а следовательно, что ${\displaystyle {\bar {t}}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}}$. Из этого следует, что q является квадратом по модулю l. Пусть ${\displaystyle q\equiv w^{2}{\pmod {l}}}$. Вычислим ${\displaystyle w\phi (x,y)}$ в ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$ и проверим, выполняется ли ${\displaystyle {\bar {q}}(x,y)=w\phi (x,y)}$. Если так, то ${\displaystyle t_{l}}$ является ${\displaystyle \pm 2w{\pmod {l}}}$, в зависимости от координаты y.

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

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

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

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

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

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

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

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