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

Алгоритм опубликовал в 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}$ .

Можно попытаться в символьном виде вычислить эти точки ${\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)}$ .

Случай 1: ${\displaystyle (x^{q^{2}},y^{q^{2}})\neq \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 .

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

Предположим, что ${\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}$

Если вспомнить, наши начальные соглашения не рассматривают случая ${\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++ Майком Скоттом и доступны в . Имплементация абсолютно свободная (никаких условий, никаких ограничений), но использует библиотеку , которая распространяется под лицензией AGPLv3 .

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

См. также

• Эллиптическая криптография
• Эндоморфизм Фробениуса

Примечания

Литература