Подсчет точек на эллиптических кривых

Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Декабрь 2023 ) ( Узнайте, как и когда удалять это сообщение )

Важным аспектом в изучении эллиптических кривых является разработка эффективных способов подсчета точек на кривой . Было несколько подходов для этого, и разработанные алгоритмы оказались полезными инструментами в изучении различных областей, таких как теория чисел , а в последнее время в криптографии и аутентификации цифровой подписи (см. криптография эллиптической кривой и DSA эллиптической кривой ). В то время как в теории чисел они имеют важные последствия в решении диофантовых уравнений , в отношении криптографии они позволяют нам эффективно использовать сложность задачи дискретного логарифмирования (DLP) для группы эллиптических кривых над конечным полем , где q  =  p ^k и p — простое число. DLP, как его стали называть, является широко используемым подходом к криптографии с открытым ключом , и сложность решения этой проблемы определяет уровень безопасности криптосистемы. В данной статье рассматриваются алгоритмы подсчета точек на эллиптических кривых над полями большой характеристики, в частности p  > 3. Для кривых над полями малой характеристики существуют более эффективные алгоритмы, основанные на p -адических методах.${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle \mathbb {F} _{q}}$

Существует несколько подходов к проблеме. Начиная с наивного подхода, мы прослеживаем развитие вплоть до окончательной работы Шуфа по этому вопросу, а также перечисляем улучшения алгоритма Шуфа, сделанные Элкисом (1990) и Аткиным (1992).

Несколько алгоритмов используют тот факт, что группы вида подчиняются важной теореме Хассе, которая ограничивает число рассматриваемых точек. Теорема Хассе утверждает, что если E — эллиптическая кривая над конечным полем , то мощность удовлетворяет условию${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle E(\mathbb {F} _{q})}$

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

Наивный подход к подсчету точек, который является наименее сложным, включает в себя прогон всех элементов поля и проверку того, какие из них удовлетворяют форме Вейерштрасса эллиптической кривой.${\displaystyle \mathbb {F} _{q}}$

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

Пусть E будет кривой y ² = x ³ + x + 1 над . Чтобы подсчитать точки на E , мы составляем список возможных значений x , затем квадратичных вычетов x mod 5 (только для целей поиска), затем x ³ + x + 1 mod 5, затем y от x ³ + x + 1 mod 5. Это дает точки на E .${\displaystyle \mathbb {F} _{5}}$

${\displaystyle x}$	${\displaystyle x^{2}}$	${\displaystyle х^{3}+х+1}$	${\displaystyle у}$	Очки
${\displaystyle \quad 0}$	${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1,4}$	${\displaystyle (0,1),(0,4)}$
${\displaystyle \quad 1}$	${\displaystyle 1}$	${\displaystyle 3}$	${\displaystyle -}$	${\displaystyle -}$
${\displaystyle \quad2}$	${\displaystyle 4}$	${\displaystyle 1}$	${\displaystyle 1,4}$	${\displaystyle (2,1),(2,4)}$
${\displaystyle \quad3}$	${\displaystyle 4}$	${\displaystyle 1}$	${\displaystyle 1,4}$	${\displaystyle (3,1),(3,4)}$
${\displaystyle \quad 4}$	${\displaystyle 1}$	${\displaystyle 4}$	${\displaystyle 2,3}$	${\displaystyle (4,2),(4,3)}$

Например, последняя строка вычисляется следующим образом: Если вы подставите в уравнение x ³ + x + 1 mod 5, то получите в качестве результата (3-й столбец). Этот результат может быть достигнут, если ( Квадратичные вычеты можно найти во 2-м столбце). Таким образом, баллы для последней строки равны .${\displaystyle x=4}$${\displaystyle 4}$${\displaystyle у=2,3}$${\displaystyle (4,2),(4,3)}$

Следовательно, имеет мощность 9: 8 перечисленных выше точек и точка в бесконечности.${\displaystyle E(\mathbb {F} _{5})}$

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

Улучшение времени выполнения достигается с помощью другого подхода: мы выбираем элемент , выбирая случайные значения до тех пор, пока не станет квадратом в , а затем вычисляем квадратный корень этого значения, чтобы получить . Теорема Хассе гласит, что лежит в интервале . Таким образом, по теореме Лагранжа нахождение уникального лежащего в этом интервале и удовлетворяющего , приводит к нахождению мощности . Алгоритм терпит неудачу, если существуют два различных целых числа и в интервале такие, что . В таком случае обычно достаточно повторить алгоритм с другой случайно выбранной точкой в ​​.${\displaystyle P=(x,y)\in E(\mathbb {F} _{q})}$${\displaystyle x}$${\displaystyle x^{3}+Ax+B}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle у}$${\displaystyle |E(\mathbb {F} _{q})|}$${\displaystyle (q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})}$${\displaystyle М}$${\displaystyle МП=О}$${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle М}$${\displaystyle М'}$${\displaystyle МП=М'П=О}$${\displaystyle E(\mathbb {F} _{q})}$

Перебор всех значений для поиска удовлетворяющего займет около шагов.${\displaystyle М}$${\displaystyle МП=О}$${\displaystyle 4{\sqrt {q}}}$

Однако, применяя алгоритм baby-step giant-step к , мы можем ускорить это до шагов. Алгоритм следующий.${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle 4{\sqrt[{4}]{q}}}$

1. выбрать целое число,
2. FOR { to } DO
3.
4. ENDFOR
5.
6.
7. REPEAT вычислить точки
8. UNTIL : \\the -координаты сравниваются${\displaystyle м}$${\displaystyle m>{\sqrt[{4}]{q}}}$${\displaystyle j=0}$${\displaystyle м}$${\displaystyle P_{j}\leftarrow jP}$${\displaystyle L\leftarrow 1}$${\displaystyle Q\leftarrow (q+1)P}$${\displaystyle Q+k(2mP)}$ ${\displaystyle \exists j}$${\displaystyle Q+k(2mP)=\pm P_{j}}$${\displaystyle x}$9. \\note
10. Фактор . Пусть будут различными простыми множителями числа .${\displaystyle M\leftarrow q+1+2mk\mp j}$${\displaystyle МП=О}$${\displaystyle М}$${\displaystyle p_{1},\ldots ,p_{r}}$${\displaystyle М}$11. WHILE  DO
12. IF
13. THEN
14. ELSE
15. ENDIF
16. ENDWHILE
17. \\note — порядок точки
18. WHILE делит более одного целого числа
19. DO выбирает новую точку и переходит к 1.${\displaystyle i\leq r}$  ${\displaystyle {\frac {M}{p_{i}}}P=O}$ ${\displaystyle M\leftarrow {\frac {M}{p_{i}}}}$ ${\displaystyle i\leftarrow i+1}$${\displaystyle L\leftarrow \operatorname {lcm} (L,M)}$${\displaystyle М}$${\displaystyle P}$ ${\displaystyle L}$${\displaystyle N}$${\displaystyle (q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})}$${\displaystyle P}$20. ENDWHILE
21. RETURN \\это мощность${\displaystyle N}$${\displaystyle E(\mathbb {F} _{q})}$

• В строке 8. мы предполагаем существование соответствия. Действительно, следующая лемма гарантирует, что такое соответствие существует:

Пусть будет целым числом с . Существуют целые числа и с${\displaystyle а}$${\displaystyle |a|\leq 2m^{2}}$${\displaystyle а_{0}}$${\displaystyle а_{1}}$

${\displaystyle -m<a_{0}\leq m{\mbox{ и }}-m\leq a_{1}\leq m{\mbox{ ст }}a=a_{0}+2ma_{1}.}$

• Вычисление после вычисления можно выполнить путем прибавления к вместо повторного вычисления полного скалярного умножения. Таким образом, полное вычисление требует сложений. может быть получено одним удвоением из . Вычисление требует удвоений и сложений, где — количество ненулевых цифр в двоичном представлении ; обратите внимание, что знание и позволяет нам сократить количество удвоений. Наконец, чтобы получить от к , просто сложите, а не пересчитывайте все.${\displaystyle (j+1)P}$${\displaystyle jP}$${\displaystyle P}$${\displaystyle jP}$${\displaystyle м}$${\displaystyle 2мП}$${\displaystyle мП}$${\displaystyle Q}$${\displaystyle \log(q+1)}$${\displaystyle w}$${\displaystyle w}$${\displaystyle д+1}$${\displaystyle jP}$${\displaystyle 2мП}$${\displaystyle Q+k(2mP)}$${\displaystyle Q+(k+1)(2mP)}$${\displaystyle 2мП}$
• Мы предполагаем, что можем разложить на множители . Если нет, то мы можем по крайней мере найти все малые простые множители и проверить это для них. Тогда будет хорошим кандидатом для порядка .${\displaystyle М}$${\displaystyle p_{i}}$${\displaystyle {\frac {M}{p_{i}}}\neq O}$${\displaystyle М}$${\displaystyle P}$
• Вывод шага 17 можно доказать с помощью элементарной теории групп: поскольку , порядок делит . Если ни один собственный делитель не реализует , то порядок равен .${\displaystyle МП=О}$${\displaystyle P}$${\displaystyle М}$${\displaystyle {\bar {M}}}$${\displaystyle М}$${\displaystyle {\bar {M}}P=O}$${\displaystyle М}$${\displaystyle P}$

Одним из недостатков этого метода является то, что требуется слишком много памяти, когда группа становится большой. Чтобы решить эту проблему, может быть более эффективно хранить только координаты точек (вместе с соответствующим целым числом ). Однако это приводит к дополнительному скалярному умножению для выбора между и .${\displaystyle x}$${\displaystyle jP}$${\displaystyle j}$${\displaystyle -j}$${\displaystyle +j}$

Существуют другие общие алгоритмы для вычисления порядка элемента группы, которые более эффективны с точки зрения использования памяти, такие как алгоритм Полларда rho и метод кенгуру Полларда . Метод кенгуру Полларда позволяет искать решение в заданном интервале, получая время выполнения , используя память.${\displaystyle O({\sqrt[{4}]{q}})}$${\displaystyle O(\log ^{2}{q})}$

Теоретический прорыв в проблеме вычисления мощности групп типа был достигнут Рене Схоофом, который в 1985 году опубликовал первый детерминированный алгоритм полиномиального времени. Центральными элементами алгоритма Схоофа являются использование полиномов деления и теоремы Хассе , а также китайской теоремы об остатках .${\displaystyle E(\mathbb {F} _{q})}$

Идея Шуфа использует тот факт, что по теореме Хассе существует конечный диапазон возможных значений для . Достаточно вычислить по модулю целое число . Это достигается путем вычисления по модулю простых чисел , произведение которых превышает , а затем применения китайской теоремы об остатках. Ключ к алгоритму — использование многочлена деления для эффективного вычисления по модулю .${\displaystyle |E(\mathbb {F} _{q})|}$${\displaystyle |E(\mathbb {F} _{q})|}$${\displaystyle N>4{\sqrt {q}}}$${\displaystyle |E(\mathbb {F} _{q})|}$${\displaystyle \ell _{1},\ldots ,\ell _{s}}$${\displaystyle 4{\sqrt {q}}}$${\displaystyle \psi _{\ell }}$${\displaystyle |E(\mathbb {F} _{q})|}$${\displaystyle \ell }$

Время выполнения алгоритма Шуфа полиномиально по , с асимптотической сложностью , где обозначает сложность целочисленного умножения . Его пространственная сложность составляет .${\displaystyle n=\log {q}}$${\displaystyle O(n^{2}M(n^{3})/\log {n})=O(n^{5+o(1)})}$${\displaystyle M(n)}$${\displaystyle O(n^{3})}$

В 1990-х годах Ноам Элкис , а затем и AOL Аткин разработали усовершенствования базового алгоритма Шуфа, сделав различие между используемыми простыми числами. Простое число называется простым числом Элкиса, если характеристическое уравнение эндоморфизма Фробениуса, , распадается на . В противном случае оно называется простым числом Аткина. Простые числа Элкиса являются ключом к улучшению асимптотической сложности алгоритма Шуфа. Информация, полученная из простых чисел Аткина, позволяет добиться дальнейшего улучшения, которое асимптотически незначительно, но может быть весьма важным на практике. Модификация алгоритма Шуфа для использования простых чисел Элкиса и Аткина известна как алгоритм Шофа–Элкиса–Аткина (SEA).${\displaystyle \ell _{1},\ldots ,\ell _{s}}$${\displaystyle \ell }$${\displaystyle \phi ^{2}-t\phi +q=0}$${\displaystyle \mathbb {F} _{\ell }}$${\displaystyle \ell }$

Статус конкретного простого числа зависит от эллиптической кривой и может быть определен с помощью модульного многочлена . Если одномерный многочлен имеет корень в , где обозначает j-инвариант , то является простым числом Элкиса, в противном случае это простой числом Аткина. В случае Элкиса дальнейшие вычисления с участием модульных многочленов используются для получения собственного множителя многочлена деления . Степень этого множителя равна , тогда как имеет степень .${\displaystyle \ell }$${\displaystyle E/\mathbb {F} _{q}}$ ${\displaystyle \Psi _{\ell }(X,Y)}$${\displaystyle \Psi _{\ell }(X,j(E))}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle j(E)}$${\displaystyle E}$${\displaystyle \ell }$${\displaystyle \psi _{\ell }}$${\displaystyle O(\ell )}$${\displaystyle \psi _{\ell }}$${\displaystyle O(\ell ^{2})}$

В отличие от алгоритма Шуфа, алгоритм SEA обычно реализуется как вероятностный алгоритм (типа Лас-Вегаса ), так что поиск корня и другие операции могут выполняться более эффективно. Его вычислительная сложность определяется стоимостью вычисления модульных многочленов , но поскольку они не зависят от , их можно вычислить один раз и использовать повторно. При эвристическом предположении, что существует достаточно много малых простых чисел Элкиса, и без учета стоимости вычисления модульных многочленов, асимптотическое время работы алгоритма SEA равно , где . Его пространственная сложность равна , но при использовании предварительно вычисленных модульных многочленов она увеличивается до .${\displaystyle \Psi _{\ell }(X,Y)}$${\displaystyle E}$${\displaystyle O(n^{2}M(n^{2})/\log {n})=O(n^{4+o(1)})}$${\displaystyle n=\log {q}}$${\displaystyle O(n^{3}\log {n})}$${\displaystyle O(n^{4})}$

• Алгоритм Шуфа
• Криптография на основе эллиптических кривых
• Маленький-шаг-гигантский-шаг
• Криптография с открытым ключом
• Алгоритм Шуфа – Элкиса – Аткина
• Поллард ро
• Кенгуру Полларда
• Доказательство простоты эллиптической кривой

• И. Блейк, Г. Серусси и Н. Смарт: Эллиптические кривые в криптографии , Cambridge University Press, 1999.
• А. Энге: Эллиптические кривые и их применение в криптографии: Введение . Kluwer Academic Publishers, Дордрехт, 1999.
• G. Musiker: Алгоритм Шуфа для подсчета очков на . Доступно по адресу http://www.math.umn.edu/~musiker/schoof.pdf${\displaystyle E(\mathbb {F} _{q})}$
• Р. Шоф: Подсчет точек на эллиптических кривых над конечными полями. J. Theor. Nombres Bordeaux 7:219-254, 1995. Доступно на http://www.mat.uniroma2.it/~schoof/ctg.pdf
• LC Washington: Эллиптические кривые: теория чисел и криптография. Chapman \& Hall/CRC, Нью-Йорк, 2003.