除算多項式

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

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

René Schoof は、番目の除算多項式を法として作業すると、すべての - ねじれ点を同時に処理できることを観察しました。これは、楕円曲線上の点を数えるSchoof のアルゴリズムで頻繁に使用されます。 ${\displaystyle \ell }$${\displaystyle \ell }$

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

• A. Enge:楕円曲線と暗号への応用: 入門Kluwer Academic Publishers、ドルドレヒト、1999 年。
• N. コブリッツ:数論と暗号学のコース、大学院数学テキスト第 114 号、Springer-Verlag、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 Washington:楕円曲線: 数論と暗号. Chapman & Hall/CRC、ニューヨーク、2003 年。
• J. シルバーマン:楕円曲線の算術、Springer-Verlag、GTM 106、1986 年。