Полиномы деления - Division polynomials

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

Определение

Набор полиномов деления представляет собой последовательность многочлены в ${displaystyle mathbb {Z} [x,y,A,B]}$ с ${displaystyle x,y,A,B}$ свободные переменные, которые рекурсивно определяются:

${displaystyle psi _{0}=0}$

${displaystyle psi _{1}=1}$

${displaystyle psi _{2}=2y}$

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

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

${displaystyle vdots }$

${displaystyle psi _{2m+1}=psi _{m+2}psi _{m}^{3}-psi _{m-1}psi _{m+1}^{3}{ ext{ for }}mgeq 2}$

${displaystyle psi _{2m}=left({frac {psi _{m}}{2y}}ight)cdot (psi _{m+2}psi _{m-1}^{2}-psi _{m-2}psi _{m+1}^{2}){ ext{ for }}mgeq 3}$

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

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

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

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

куда ${displaystyle phi _{n}}$ и ${displaystyle omega _{n}}$ определяются:

${displaystyle phi _{n}=xpsi _{n}^{2}-psi _{n+1}psi _{n-1},}$

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

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

Позволять ${displaystyle p>3}$ быть первоклассным и позволить ${displaystyle E:y^{2}=x^{3}+Ax+B}$ быть эллиптическая кривая над конечным полем ${displaystyle mathbb {F} _{p}}$, т.е. ${displaystyle A,Bin mathbb {F} _{p}}$. В ${displaystyle ell }$-кручение группы ${displaystyle E}$ над ${displaystyle {ar {mathbb {F} }}_{p}}$ является изоморфный к ${displaystyle mathbb {Z} /ell imes mathbb {Z} /ell }$ если ${displaystyle ell eq p}$, и чтобы ${displaystyle mathbb {Z} /ell }$ или же ${displaystyle {0}}$ если ${displaystyle ell =p}$. Следовательно, степень ${displaystyle psi _{ell }}$ равно либо ${displaystyle {frac {1}{2}}(l^{2}-1)}$, ${displaystyle {frac {1}{2}}(l-1)}$, или 0.

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

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

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

Рекомендации

• А. Энге: Эллиптические кривые и их приложения в криптографии: введение. Kluwer Academic Publishers, Дордрехт, 1999.
• Н. Коблиц: Курс теории чисел и криптографии, Тексты для выпускников по математике. № 114, Springer-Verlag, 1987. Издание второе, 1994.
• Мюллер: Die Berechnung der Punktanzahl von elliptischen kurvenüber endlichen Primkörpern. Дипломная работа. Universität des Saarlandes, Саарбрюккен, 1991.
• Г. Мюзикер: Алгоритм Шуфа для подсчета очков на ${displaystyle E(mathbb {F} _{q})}$. Доступны на http://www-math.mit.edu/~musiker/schoof.pdf^{[постоянная мертвая ссылка ]}
• Скуф: Эллиптические кривые над конечными полями и вычисление квадратных корней по модулю p. Математика. 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
• Л. С. Вашингтон: Эллиптические кривые: теория чисел и криптография. Chapman & Hall / CRC, Нью-Йорк, 2003.
• Дж. Сильверман: Арифметика эллиптических кривых, Springer-Verlag, GTM 106, 1986.