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

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

Определение [ править ]

Набор деления многочленов представляет собой последовательность многочленов в с свободными переменными , который рекурсивно определяется по формуле:${\ Displaystyle \ mathbb {Z} [х, у, А, В]}$${\ Displaystyle х, у, А, В}$

${\ 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}{\text{ for }}m\geq 2}$

${\displaystyle \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}$

Многочлен называется n- ^м многочленом деления.${\displaystyle \psi _{n}}$

Свойства [ править ]

• На практике один устанавливает , а потом и .${\displaystyle y^{2}=x^{3}+Ax+B}$${\displaystyle \psi _{2m+1}\in \mathbb {Z} [x,A,B]}$${\displaystyle \psi _{2m}\in 2y\mathbb {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,B\in 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)^{\text{th}}}$ ${\displaystyle E}$${\displaystyle \psi _{2n}/y}$${\displaystyle x}$${\displaystyle E[2n]\setminus E[2]}$
• Учитывая точку на эллиптической кривой над некоторым полем , мы можем выразить координаты n- ^го кратного числа через полиномы деления:${\displaystyle P=(x_{P},y_{P})}$${\displaystyle E:y^{2}=x^{3}+Ax+B}$${\displaystyle K}$${\displaystyle P}$

${\displaystyle 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)}$

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

${\displaystyle \phi _{n}=x\psi _{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]}$

Позвольте быть простым и пусть быть эллиптической кривой над конечным полем , т . Е .. Кручение группа за кадром является изоморфной , чтобы , если , и или если . Следовательно , степень равна либо , или 0.${\displaystyle p>3}$${\displaystyle E:y^{2}=x^{3}+Ax+B}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle A,B\in \mathbb {F} _{p}}$${\displaystyle \ell }$${\displaystyle E}$${\displaystyle {\bar {\mathbb {F} }}_{p}}$${\displaystyle \mathbb {Z} /\ell \times \mathbb {Z} /\ell }$${\displaystyle \ell \neq 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)}$

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

См. Также [ править ]

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

Ссылки [ править ]

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