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

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

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

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

Введение

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

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

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

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

Основная статья: теорема Хассе об эллиптических кривых

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

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

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

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

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

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

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

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

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

$\phi ^{2}-t\phi +q=0,$ где $t=q+1-\#E(\mathbb {F} _{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 {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)$ из $E$ а затем найдите значение $t$ что удовлетворяет уравнению. Однако степени становятся очень большими, и такой подход непрактичен.

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

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

где ${\bar {t}}$ и ${\bar {q}}$ иметь целочисленные значения в $[-(l-1)/2,(l-1)/2]$.

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

Многочлен l -го деления таков, что его корнями являются в точности координаты x точек порядка l . Таким образом, чтобы ограничить вычисление $(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ к точкам l -кручения означает вычисление этих выражений как функций в координатном кольце E и по модулю l -го полинома деления. Т.е. мы работаем в $\mathbb {F} _{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}})+{\bar {q}}(x,y)$ не более 1 по y и не более $(l^{2}-3)/2$ в х .

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

${\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)$

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

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

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

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

$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, чтобы сузить выбор. ${\bar {t}}$ к двум возможностям, а именно положительному и отрицательному случаю. Используя координату y, позже определяется, какой из двух случаев имеет место.

Сначала мы покажем, что X является функцией только от x . Учитывать $(y^{q^{2}}-y_{\bar {q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {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)){\bmod {\psi }}_{l}(x).$

Тут вроде не правильно, выбрасываем $x^{q^{2}}-x_{\bar {q}}$?

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

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

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

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

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

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

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

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

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

Алгоритм

    Input:
        1. An elliptic curve $E=y^{2}-x^{3}-Ax-B$.
        2. An integer q for a finite field $F_{q}$ with $q=p^{b},b\geq 1$.
    Output:
        The number of points of E over $F_{q}$.
    Choose a set of odd primes S not containing p such that $N=\prod _{l\in S}l>4{\sqrt {q}}.$
    Put $t_{2}=0$ if $\gcd(x^{q}-x,x^{3}+Ax+B)\neq 1$, else $t_{2}=1$.
    Compute the division polynomial $\psi _{l}$. 
    All computations in the loop below are performed in the ring $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).$
    For $l\in S$ do:
        Let ${\bar {q}}$ be the unique integer such that  $q\equiv {\bar {q}}{\pmod {l}}$ and $\mid {\bar {q}}\mid <l/2$.
        Compute $(x^{q},y^{q})$, $(x^{q^{2}},y^{q^{2}})$ and $(x_{\bar {q}},y_{\bar {q}})$.   
        if $x^{q^{2}}\neq x_{\bar {q}}$ then
            Compute $(X,Y)$.
            for $1\leq {\bar {t}}\leq (l-1)/2$ do:
                if $X=x_{\bar {t}}^{q}$ then
                    if $Y=y_{\bar {t}}^{q}$ then
                        $t_{l}={\bar {t}}$;
                    else
                        $t_{l}=-{\bar {t}}$.
        else if q is a square modulo l then
            compute w with $q\equiv w^{2}{\pmod {l}}$
            compute $w(x^{q},y^{q})$
            if $w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})$ then
                $t_{l}=2w$
            else if $w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})$ then
                $t_{l}=-2w$
            else
                $t_{l}=0$
        else
            $t_{l}=0$
    Use the Chinese Remainder Theorem to compute t modulo N
        from the equations $t\equiv t_{l}{\pmod {l}}$, where $l\in S$.
    Output $q+1-t$.

Сложность

Большая часть вычислений занимает оценка $\phi (P)$ и $\phi ^{2}(P)$, для каждого простого числа $l$, это вычисления $x^{q}$, $y^{q}$, $x^{q^{2}}$, $y^{q^{2}}$ для каждого простого числа $l$. Это включает возведение в степень в кольце $R=\mathbb {F} _{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 {F} _{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},\ldots ,l_{s}\}$ рассмотренные ранее простые числа определенного вида. Их стали называть простыми числами Элкиса и простыми числами Аткина соответственно. Премьер $l$ называется простым числом Элкиса, если характеристическое уравнение: $\phi ^{2}-t\phi +q=0$ раскалывается $\mathbb {F} _{l}$, а простое число Аткина — это простое число, не являющееся простым числом Элкиса. Аткин показал, как объединить информацию, полученную из простых чисел Аткина, с информацией, полученной из простых чисел Элкиса, для создания эффективного алгоритма, который стал известен как алгоритм Шуфа – Элкиса – Аткина . Первая проблема, которую необходимо решить, — определить, является ли данное простое число Элкисом или Аткином. Для этого мы используем модульные полиномы, которые возникли в результате изучения модулярных форм и интерпретации эллиптических кривых над комплексными числами как решеток. Как только мы определили, в каком случае мы находимся, вместо использования полиномов деления мы можем работать с полиномом, который имеет более низкую степень, чем соответствующий полином деления: $O(l)$ скорее, чем $O(l^{2})$. Для эффективной реализации используются вероятностные алгоритмы поиска корней, что делает этот алгоритм Лас-Вегаса, а не детерминированным алгоритмом. При эвристическом предположении, что примерно половина простых чисел до $O(\log q)$ связаны простые числа Элкиса, это дает алгоритм, который более эффективен, чем алгоритм Шуфа, с ожидаемым временем работы $O(\log ^{6}q)$ используя наивную арифметику и ${\tilde {O}}(\log ^{4}q)$ используя быструю арифметику. Хотя известно, что это эвристическое предположение справедливо для большинства эллиптических кривых, известно, что оно выполняется не во всех случаях, даже при GRH .

Реализации

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

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

См. также

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

Ссылки

• Р. Шуф: Эллиптические кривые над конечными полями и вычисление квадратных корней мод. с. Математика. Comp., 44(170):483–494, 1985. Доступно по адресу http://www.mat.uniroma2.it/~schoof/ctpts.pdf.
• Р. Шуф: Подсчет точек на эллиптических кривых над конечными полями. Дж. Теория. Nombres Bordeaux 7:219–254, 1995. Доступно по адресу http://www.mat.uniroma2.it/~schoof/ctg.pdf.
• Г. Мюзикер: Алгоритм Шуфа для подсчета очков на $E(\mathbb {F} _{q})$. Доступно по адресу http://www.math.umn.edu/~musiker/schoof.pdf.
• В. Мюллер: Вычисление количества точек эллиптических кривых над конечными простыми телами. Магистерская диссертация. Саарский университет, Саарбрюккен, 1991 г. Доступно по адресу http://lecturer.ukdw.ac.id/vmueller/publications.php.
• А. Энге: Эллиптические кривые и их приложения в криптографии: Введение. Kluwer Academic Publishers, Дордрехт, 1999.
• Л. К. Вашингтон: Эллиптические кривые: теория чисел и криптография. Чепмен и Холл/CRC, Нью-Йорк, 2003 г.
• Н. Коблиц: Курс теории чисел и криптографии, Тексты для аспирантов по математике. № 114, Springer-Verlag, 1987. Второе издание, 1994 г.