除算多項式

数学において、除算多項式は楕円曲線上の点の倍数を計算し、捩れ点によって生成される体を研究する方法を提供します。これらは、シューフのアルゴリズムにおける楕円曲線上の点の数え上げの研究において中心的な役割を果たします。

意味

除算多項式の集合は、次のように再帰的に定義される自由変数を持つ多項式の列です。 ${\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}{\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 }$

参照

• シューフのアルゴリズム

参考文献

• A. エンゲ『楕円曲線と暗号への応用：入門』 Kluwer Academic Publishers、ドルドレヒト、1999年。
• N. コブリッツ：数論と暗号学講座、大学院数学テキスト第114号、シュプリンガー・フェアラーク、1987年。第2版、1994年
• ミュラー : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern。修士論文。ザールランデス大学、ザールブリュッケン、1991 年。
• G. Musiker: Schoof の点計算アルゴリズム ${\displaystyle E(\mathbb {F} _{q})}$。https://www-users.cse.umn.edu/~musiker/schoof.pdf で入手可能。
• Schoof:有限体上の楕円曲線とpを法とする平方根の計算. Math. Comp., 44(170):483–494, 1985. http://www.mat.uniroma2.it/~schoof/ctpts.pdf で入手可能
• R. Schoof:有限体上の楕円曲線上の点の数え上げ. J. Theor. Nombres Bordeaux 7:219–254, 1995. http://www.mat.uniroma2.it/~schoof/ctg.pdf で入手可能
• LCワシントン：楕円曲線：数論と暗号.Chapman & Hall/CRC, ニューヨーク, 2003年.
• J. シルバーマン：楕円曲線の算術、Springer-Verlag、GTM 106、1986年。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Division_polynomials&oldid=1289128105"