Подсчет точек на эллиптических кривых - Counting points on elliptic curves

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

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

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

Некоторые алгоритмы используют тот факт, что группы формы ${displaystyle E (mathbb {F} _ {q})}$ подпадают под важную теорему Хассе, ограничивающую количество рассматриваемых точек. Теорема Хассе заявляет, что если E является эллиптической кривой над конечным полем ${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 быть кривой у² = Икс³ + Икс +1 больше ${displaystyle mathbb {F} _ {5}}$ . Для подсчета очков E, составим список возможных значений Икс, затем квадратичные вычеты из x mod 5 (только для поиска), затем из Икс³ + Икс + 1 мод 5, затем из у из Икс³ + Икс + 1 mod 5. Это дает очки на E.

${displaystyle x}$	${displaystyle x ^ {2}}$	${displaystyle x ^ {3} + x + 1}$	${displaystyle y}$	Точки
${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 quad 2}$	${displaystyle 4}$	${displaystyle 1}$	${displaystyle 1,4}$	${displaystyle (2,1), (2,4)}$
${displaystyle quad 3}$	${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)}$

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

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

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

Бэби-степ гигантский шаг

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

Испытание всех значений ${displaystyle M}$ чтобы найти тот, который удовлетворяет ${displaystyle MP = O}$ принимает вокруг ${displaystyle 4 {sqrt {q}}}$ шаги.

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

Алгоритм

1. выберите  ${displaystyle m}$  целое число  ${displaystyle m> {sqrt [{4}] {q}}}$ 2. ЗА{ ${displaystyle j = 0}$  к  ${displaystyle m}$ } ДЕЛАТЬ 3.     ${displaystyle P_ {j} leftarrow jP}$ 4. ENDFOR5.  ${displaystyle Lleftarrow 1}$ 6.  ${displaystyle Qleftarrow (q + 1) P}$ 7. ПОВТОРЕНИЕ вычислить точки  ${displaystyle Q + k (2mP)}$ 8. ДО ТОГО КАК  ${displaystyle существует j}$ :  ${displaystyle Q + k (2mP) = pm P_ {j}}$    the  ${displaystyle x}$ -координаты сравниваются 9.  ${displaystyle Mleftarrow q + 1 + 2mkmp j}$      Примечание  ${displaystyle MP = O}$ 10. Фактор  ${displaystyle M}$ . Позволять  ${displaystyle p_ {1}, ldots, p_ {r}}$  - различные простые множители  ${displaystyle M}$ .11. ПОКА  ${displaystyle ileq r}$  ДЕЛАТЬ12.    ЕСЛИ  ${displaystyle {frac {M} {p_ {i}}} P = O}$ 13.       ТОГДА  ${displaystyle Mleftarrow {frac {M} {p_ {i}}}}$ 14.       ЕЩЕ  ${displaystyle ileftarrow i + 1}$  15.    ENDIF16. ENDWHILE17.  ${displaystyle Lleftarrow operatorname {lcm} (L, M)}$      Примечание  ${displaystyle M}$  это порядок точки  ${displaystyle P}$ 18. ПОКА  ${displaystyle L}$  делит более одного целого числа  ${displaystyle N}$  в  ${displaystyle (q + 1-2 {sqrt {q}}, q + 1 + 2 {sqrt {q}})}$ 19.    ДЕЛАТЬ выберите новую точку  ${displaystyle P}$  и перейдите к 1.20. ENDWHILE21. ВОЗВРАЩАТЬСЯ  ${displaystyle N}$       это мощность  ${displaystyle E (mathbb {F} _ {q})}$

Примечания к алгоритму

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

Позволять

{displaystyle a}

быть целым числом с

{displaystyle | a | leq 2m ^ {2}}

. Есть целые числа

{displaystyle a_ {0}}

и

{displaystyle a_ {1}}

с

{displaystyle -m

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

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

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

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

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

Понимание Шуфа использует тот факт, что по теореме Хассе существует конечный диапазон возможных значений для ${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-е годы Ноам Элкис, с последующим Аткин А.О. разработал улучшения основного алгоритма Шуфа, проводя различие между простыми числами ${displaystyle ell _ {1}, ldots, ell _ {s}}$ которые используются. Премьер ${displaystyle ell}$ называется простым числом Элкиса, если характеристическое уравнение эндоморфизма Фробениуса ${displaystyle phi ^ {2} -tphi + q = 0}$ , разделяется на ${displaystyle mathbb {F} _ {ell}}$ . Иначе ${displaystyle ell}$ называется простым числом Аткина. Простые числа Элкиса являются ключом к улучшению асимптотической сложности алгоритма Шуфа. Информация, полученная с помощью простых чисел Аткина, допускает дальнейшее улучшение, которое асимптотически незначительно, но может быть весьма важным на практике. Модификация алгоритма Шуфа для использования простых чисел Элкиса и Аткина известна как алгоритм Шуфа – Элкиса – Аткина (SEA).

Статус конкретного прайма ${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)}$ обозначает j-инвариантный из ${displaystyle E}$ , тогда ${displaystyle ell}$ является простым числом Элкиса, в противном случае - простым числом Аткина. В случае Элкиса для получения правильного множителя полинома деления используются дальнейшие вычисления с участием модулярных полиномов ${displaystyle psi _ {ell}}$ . Степень этого фактора составляет ${displaystyle O (ell)}$ , в то время как ${displaystyle psi _ {ell}}$ имеет степень ${displaystyle O (ell ^ {2})}$ .

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

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

Библиография

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