Полиномы деления

В математике полиномы деления позволяют вычислять кратные точки на эллиптических кривых и изучать поля, создаваемые точками кручения. Они играют центральную роль при изучении подсчета точек на эллиптических кривых в алгоритме Шуфа .

Определение

Множество полиномов деления представляет собой последовательность полиномов от $\mathbb {Z} [x,y,A,B]$ с $x,y,A,B$ свободные переменные, которые рекурсивно определяются следующим образом:

$\psi _{0}=0$

$\psi _{1}=1$

$\psi _{2}=2y$

$\psi _{3}=3x^{4}+6Ax^{2}+12Bx-A^{2}$

$\psi _{4}=4y(x^{6}+5Ax^{4}+20Bx^{3}-5A^{2}x^{2}-4ABx-8B^{2}-A^{3})$

$\vdots$

$\psi _{2m+1}=\psi _{m+2}\psi _{m}^{3}-\psi _{m-1}\psi _{m+1}^{3}{\text{ for }}m\geq 2$

$\psi _{2m}=\left({\frac {\psi _{m}}{2y}}\right)\cdot (\psi _{m+2}\psi _{m-1}^{2}-\psi _{m-2}\psi _{m+1}^{2}){\text{ for }}m\geq 3$

Полином $\psi _{n}$ называется н ^й полином деления.

Характеристики

• На практике устанавливают $y^{2}=x^{3}+Ax+B$, а потом $\psi _{2m+1}\in \mathbb {Z} [x,A,B]$ и $\psi _{2m}\in 2y\mathbb {Z} [x,A,B]$.
• Полиномы деления образуют общую эллиптическую последовательность делимости над кольцом. $\mathbb {Q} [x,y,A,B]/(y^{2}-x^{3}-Ax-B)$.
• Если эллиптическая кривая $E$ задается в форме Вейерштрасса $y^{2}=x^{3}+Ax+B$ над каким-то полем $K$, то есть $A,B\in K$, можно использовать эти значения $A,B$ и рассмотрим полиномы деления в координатном кольце $E$. Корни $\psi _{2n+1}$ являются $x$-координаты точек $E[2n+1]\setminus \{O\}$, где $E[2n+1]$ это $(2n+1)^{\text{th}}$ торсионная подгруппа $E$. Аналогично, корни $\psi _{2n}/y$ являются $x$-координаты точек $E[2n]\setminus E[2]$.
• Учитывая точку $P=(x_{P},y_{P})$ на эллиптической кривой $E:y^{2}=x^{3}+Ax+B$ над каким-то полем $K$, мы можем выразить координаты n ^й кратный $P$ в терминах полиномов деления:

$nP=\left({\frac {\phi _{n}(x)}{\psi _{n}^{2}(x)}},{\frac {\omega _{n}(x,y)}{\psi _{n}^{3}(x,y)}}\right)=\left(x-{\frac {\psi _{n-1}\psi _{n+1}}{\psi _{n}^{2}(x)}},{\frac {\psi _{2n}(x,y)}{2\psi _{n}^{4}(x)}}\right)$

где $\phi _{n}$ и $\omega _{n}$ определяются:

$\phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},$

$\omega _{n}={\frac {\psi _{n+2}\psi _{n-1}^{2}-\psi _{n-2}\psi _{n+1}^{2}}{4y}}.$

Используя соотношение между $\psi _{2m}$ и $\psi _{2m+1}$, наряду с уравнением кривой, функции $\psi _{n}^{2}$ , ${\frac {\psi _{2n}}{y}},\psi _{2n+1}$, $\phi _{n}$ все внутри $K[x]$.

Позволять $p>3$ будь простым и позволь $E:y^{2}=x^{3}+Ax+B$ — эллиптическая кривая над конечным полем $\mathbb {F} _{p}$, то есть, $A,B\in \mathbb {F} _{p}$. $\ell$-торсионная группа $E$ над ${\bar {\mathbb {F} }}_{p}$ изоморфен ​ ​ $\mathbb {Z} /\ell \times \mathbb {Z} /\ell$ если $\ell \neq p$, и чтобы $\mathbb {Z} /\ell$ или $\{0\}$ если $\ell =p$. Отсюда и степень $\psi _{\ell }$ равно либо ${\frac {1}{2}}(l^{2}-1)$, ${\frac {1}{2}}(l-1)$, или 0.

Рене Шуф заметил, что работа по модулю $\ell$Полином деления позволяет работать со всеми $\ell$-точки кручения одновременно. Это широко используется в алгоритме Шуфа для подсчета точек на эллиптических кривых.

См. также

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

Ссылки

• А. Энге: Эллиптические кривые и их приложения в криптографии: Введение . Kluwer Academic Publishers, Дордрехт, 1999.
• Н. Коблиц: Курс теории чисел и криптографии , Тексты для аспирантов по математике. № 114, Springer-Verlag, 1987. Второе издание, 1994 г.
• Мюллер: Вычисление количества точек эллиптических кривых над конечными простыми телами . Магистерская диссертация. Саарский университет, Саарбрюккен, 1991 г.
• Г. Мюзикер: Алгоритм Шуфа для подсчета очков на $E(\mathbb {F} _{q})$. Доступно по адресу https://www-users.cse.umn.edu/~musiker/schoof.pdf.
• Шуф: Эллиптические кривые над конечными полями и вычисление квадратных корней mod p . Математика. 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.
• Л. К. Вашингтон: Эллиптические кривые: теория чисел и криптография . Чепмен и Холл/CRC, Нью-Йорк, 2003 г.
• Дж. Сильверман: Арифметика эллиптических кривых , Springer-Verlag, GTM 106, 1986.