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

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

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

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

Введение

Пусть будет эллиптическим кривым, определенным над конечным полем , где для простого и целого числа . Над полем характеристики эллиптическую кривую можно задать (коротким) уравнением Вейерштрасса ${\displaystyle E}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q=p^{n}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle \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 \#E(\mathbb {F} _{q})}$

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

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

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

Этот мощный результат, полученный Хассе в 1934 году, упрощает нашу проблему, сужая ее до конечного (хотя и большого) набора возможностей. Определяя как , и используя этот результат, мы теперь имеем, что вычисление значения по модулю , где , достаточно для определения , и, таким образом , . Хотя не существует эффективного способа непосредственного вычисления для общего , можно вычислить для небольшого простого числа довольно эффективно. Мы выбираем быть набором различных простых чисел, таким образом, что . Учитывая для всех , китайская теорема об остатках позволяет нам вычислить . ${\displaystyle \#E(\mathbb {F} _{q})}$ ${\displaystyle t}$ ${\displaystyle q+1-\#E(\mathbb {F} _{q})}$ ${\displaystyle t}$ ${\displaystyle N}$ ${\displaystyle N>4{\sqrt {q}}}$ ${\displaystyle t}$ ${\displaystyle \#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-\#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 . Таким образом, ограничение вычисления l -точками кручения означает вычисление этих выражений как функций в кольце координат E и по модулю многочлена l -го деления. То есть мы работаем в . Это означает, в частности, что степень X и Y , определенная через , не превышает 1 по y и не превышает 1 по x . ${\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$ ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$ ${\displaystyle (X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$ ${\displaystyle (l^{2}-3)/2}$

Скалярное умножение можно выполнить либо с помощью методов удвоения и сложения , либо с помощью многочлена деления th. Последний подход дает: ${\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)}$

где — полином n -го деления. Обратите внимание, что — это функция только от x , и обозначьте ее как . ${\displaystyle \psi _{n}}$ ${\displaystyle y_{\bar {q}}/y}$ ${\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 \psi _{l}}$

Случай 1: ( x q 2 , y q 2 ) ≠ ± q ¯ ( x , y ) {\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 -координату, чтобы сузить выбор до двух возможностей, а именно положительного и отрицательного случая. Используя y -координату, позже определяется, какой из двух случаев имеет место. ${\displaystyle {\bar {t}}}$

Сначала покажем, что 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^{q^{2}}-x_{\bar {q}}}$

Теперь, если для одного , то удовлетворяет ${\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}$

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

Как упоминалось ранее, используя Y и мы теперь можем определить, какое из двух значений ( или ) работает. Это дает значение . Алгоритм Шуфа сохраняет значения в переменной для каждого рассматриваемого простого числа l . ${\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}}$

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

Начнем с предположения, что . Поскольку l — нечетное простое число, то оно не может быть таким, и, таким образом , . Характеристическое уравнение дает, что . И, следовательно, что . Это означает, что q — квадрат по модулю l . Пусть . Вычислим и проверим, является ли . Если да, то зависит от координаты y. ${\displaystyle (x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)}$ ${\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}}}$ ${\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}}}$

Если 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}$

Дополнительный случай l = 2 {\displaystyle l=2}

Если вы помните, наши первоначальные соображения опускают случай . Поскольку мы предполагаем, что q нечетно, и, в частности, тогда и только тогда, когда имеет элемент порядка 2. По определению сложения в группе любой элемент порядка 2 должен иметь вид . Таким образом, тогда и только тогда, когда многочлен имеет корень в , тогда и только тогда, когда . ${\displaystyle l=2}$ ${\displaystyle q+1-t\equiv t{\pmod {2}}}$ ${\displaystyle t_{2}\equiv 0{\pmod {2}}}$ ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle (x_{0},0)}$ ${\displaystyle t_{2}\equiv 0{\pmod {2}}}$ ${\displaystyle x^{3}+Ax+B}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \gcd(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}}.}$ Положим  if , else .  ${\displaystyle t_{2}=0}$   ${\displaystyle \gcd(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}).}$ Для  do :  ${\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)}$ для  do :  ${\displaystyle 1\leq {\bar {t}}\leq (l-1)/2}$  если  то  ${\displaystyle X=x_{\bar {t}}^{q}}$  если  то ${\displaystyle Y=y_{\bar {t}}^{q}}$   ; иначе . иначе если q является квадратом по модулю l , то вычислить w с помощью compute если то иначе если то иначе иначе Используйте китайскую теорему об остатках , чтобы вычислить t по модулю N из уравнений , где . ${\displaystyle t_{l}={\bar {t}}}$   ${\displaystyle t_{l}=-{\bar {t}}}$     ${\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}$ ${\displaystyle t\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-х годах Ноам Элкис , а затем и А. О. Л. Аткин , разработали усовершенствования базового алгоритма Шуфа, ограничив набор рассмотренных ранее простых чисел простыми числами определенного вида. Они стали называться простыми числами Элкиса и простыми числами Аткина соответственно. Простое число называется простым числом Элкиса, если характеристическое уравнение: распадается на , в то время как простым числом Аткина является простое число, которое не является простым числом Элкиса. Аткин показал, как объединить информацию, полученную из простых чисел Аткина, с информацией, полученной из простых чисел Элкиса, чтобы создать эффективный алгоритм, который стал известен как алгоритм Шуфа–Элкиса–Аткина . Первая проблема, которую нужно решить, — это определить, является ли заданное простое число простым числом Элкиса или Аткина. Для этого мы используем модульные многочлены, которые получены из изучения модульных форм и интерпретации эллиптических кривых над комплексными числами как решетками. Как только мы определили, в каком случае мы находимся, вместо использования полиномов деления мы можем работать с полиномом, который имеет меньшую степень, чем соответствующий полином деления: вместо . Для эффективной реализации используются вероятностные алгоритмы поиска корней, что делает этот алгоритм Лас-Вегаса, а не детерминированным алгоритмом. При эвристическом предположении, что примерно половина простых чисел до границы являются простыми числами Элки, это дает алгоритм, который эффективнее алгоритма Шуфа, с ожидаемым временем выполнения с использованием наивной арифметики и использованием быстрой арифметики. Хотя известно, что это эвристическое предположение справедливо для большинства эллиптических кривых, известно, что оно справедливо не во всех случаях, даже при GRH . ${\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}})}$

Смотрите также

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

Ссылки

• Р. Шуф: Эллиптические кривые над конечными полями и вычисление квадратных корней mod p. Math. Comp., 44(170):483–494, 1985. Доступно на http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• Р. Шоф: Подсчет точек на эллиптических кривых над конечными полями. J. Theor. Nombres Bordeaux 7:219–254, 1995. Доступно на http://www.mat.uniroma2.it/~schoof/ctg.pdf
• G. Musiker: Алгоритм Шуфа для подсчета очков на . Доступно по адресу http://www.math.umn.edu/~musiker/schoof.pdf ${\displaystyle E(\mathbb {F} _{q})}$
• В. Мюллер: Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Магистерская диссертация. Universität des Saarlandes, Саарбрюккен, 1991 г. Доступно по адресу http://lecturer.ukdw.ac.id/vmueller/publications.php.
• А. Энге: Эллиптические кривые и их применение в криптографии: Введение. Kluwer Academic Publishers, Дордрехт, 1999.
• LC Washington: Эллиптические кривые: теория чисел и криптография. Chapman & Hall/CRC, Нью-Йорк, 2003.
• Н. Коблиц: Курс теории чисел и криптографии, Graduate Texts in Math. № 114, Springer-Verlag, 1987. Второе издание, 1994