분할 다항식

수학에서 분할 다항식은 타원 곡선상의 점의 배수를 계산하고 비틀림 점으로 생성된 필드를 연구하는 방법을 제공한다. 그들은 Schoof의 알고리즘에서 타원곡선의 점수를 세는 연구에 중심적인 역할을 한다.

정의

분할 다항식 집합은 $Z{\displaystyle \mathbb{}}$[ ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle A}$, ${\displaystyle B}$ ${\displaystyle ]}$ ${\displaystyle \mathb {Z}[x,y,A,B]$과 x${\displaystyle }$,${\displaystyle y}$, ${\displaystyle B}$ , ${\displaystyle x,y,A,B}$ 자유$$ 변수에서 다음과 같이 반복적으로 정의된 다항식의 시퀀스입니다.

${\displaystyle \filename _{0}=0}$

${\displaystyle \filename _{1}=1}$

${\displaystyle \filename _{2}=2y}$

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

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

$\displaystyle \vdots }$

${\displaystyle \property_{2m+1}=\properties _{m+2}\properties _{m}-\properties _{m-1}properties _{m+1}^{3]}{\text{{{}m\geq 2}의 경우$

${\displaystyle \i1}{2m}=\left\frac {\reft_{m}{2}}:\right)\cdot(\ft_{m+2}\ft_{m-1}^{m-1}-\i1}{m+1}^{2}-light}{}}}}\text{{}}}}}}}}{}}}}}}}}}}}}}}}\text}}}$

다항식 ${\displaystyle {\psi n}_{}}$ ${\$을 n분법^th 다항식이라고 한다$$.

특성.

• 실제로 y ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$+ ${\displaystyle A}$+ ${\displaystyle B}$ ${\displaystyle y^{2}=x^{3}+$를 설정한다.$Ax+B}$, and then ${\displaystyle \psi _{2m+1}\in \mathbb {Z} [x,A,B]}$ and ${\displaystyle \psi _{2m}\in 2y\mathbb {Z} [x,A,B]}$.
• 분할 다항식은 링 $Q{\displaystyle \mathbb{}}$[ ${\displaystyle x,}$ ${\displaystyle y,}$ ${\displaystyle A,}$ ${\displaystyle B}$ ${\displaystyle ]}$/${\displaystyle }$( ${\displaystyle {y\mathrm{}}^{}}$ ${\displaystyle {}^{}}$- ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$- ${\displaystyle A}$- B${\displaystyle }$) ${\displaystyle \mathb {Q}[x,y,A,B]/(y^{2}-x^{3}-Ax-B)}$에 걸쳐 일반적인 타원형 불능 시퀀스를 형성한다$.$
• 타원 곡선 $E{\displaystyle }$ ${\displaystyle E}$이(가) Weierstrass $형식{\displaystyle {}^{}}$ y ${\displaystyle {2\mathrm{}}^{}}$= x ${\displaystyle {3\mathrm{}}^{}}$+ ${\displaystyle A}$+ ${\displaystyle B}$ ${\displaystyle y^{2}=x^{3}+$에 제공된 경우일부$$ 필드 $K{\displaystyle }$ ${\displaystyle$ K$\},$ 즉 $A{\displaystyle ,}$ ${\displaystyle B}$ $∈$ K${\displaystyle }${\$displaystyle A,B\in$ K$\}$에 대한 $Ax+B}$은(는) $A{\displaystyle ,}$ ${\displaystyle B}$ ${\displaystyle A,B}$의 값을 사용할 수 있으며$$ $E{\displaystyle }$ ${\displaystyle E}$의 좌표 링에서 분할 다항식을 고려할 수 있다$.$ The roots of ${\displaystyle \psi _{2n+1}}$ are the ${\displaystyle x}$-coordinates of the points of ${\displaystyle E[2n+1]\setminus \{O\}}$, where ${\displaystyle E[2n+1]}$ is the ${\displaystyle (2n+1)^{\text{th}}}$ torsion subgroup of ${$$\$$displaystyle E$$}$과 ${\displaystyle 비슷하게}$$,$ $display{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{2n}}_{}}$/ y ${\displaystyle \psi _{2n}/y}$의 뿌리는 E${\displaystyle }$[ ${\displaystyle \mathrm{2n}}$ ]${\displaystyle \setminus }$ $[2n]\setminus E[2]}$의 포인트에 $대한{\displaystyle }$ x$${\$displaystystystyle$ x$}$이다$.$
• $타원곡선{\displaystyle }$E : ${\displaystyle {y\mathrm{}}^{}}$ = ${\displaystyle {}^{}{3\mathrm{}}^{}}$ +${\displaystyle A}$ + ${\displaystyle B}${\$displaystyle E:y^{$2}=$x^{3}+$에 점 $P{\displaystyle }$=${\displaystyle }$( ${\displaystyle x_{}}$P , y${\displaystyle {}_{}}$P ) ${\displaystyle$ P$=(x_{P$},$y_{P}}}}}}}}$을(를)일부 필드 $K{\displaystyle }$ ${\displaystyle K}$에 대한 $Ax+B$$\},$ $분할{\displaystyle }$ 다항식 $측면$에서 P {\displaystyle $P}$의^th n 배수의 좌표를 표시할$$ 수 있다.

${\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 {\varphi n}_{}}$ ${\$ 및 ${\displaystyle {\Omega }_{}}$ n ${\$은(는) 다음에 의해 정의된다$$.

${\displaystyle \phi _{n}=x\pair _{n}^{2}-\pair _{n+1}\pair _{n-1}}$

${\displaystyle \omega_{n}={\frac {\frac _{n+2}\properties _{n-1}^{n-1}^{n-2}-\properties _{n+1}^{4y}}}}.}$

Using the relation between ${\displaystyle \psi _{2m}}$ and ${\displaystyle \psi _{2m+1}}$, along with the equation of the curve, the functions ${\displaystyle \psi _{n}^{2}}$ , ${\displaystyle {\frac {\psi _{2n}}{y}},\psi _{2n+1}}$, ${\displays$$tyle \phi _{n}$은(는) 모두 K${\displaystyle }$[ ${\displaystyle x}$ {\$displaystyle$ K$[x$]} 에 있다$.$

> ${\displaystyle p>3}$을(를) prime으로 하고 $E{\displaystyle }$: ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$+ ${\displaystyle A}$ x${\displaystyle }$+ B ${\displaystyle E:y^{2}=x^{3}+$로 한다.$Ax+B}$은(는) 유한장 $F{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$ \$mathb {F}$ _${p$ 즉 $A{\displaystyle ,}$ ${\displaystyle B}$ ${\displaystyle \in }$ ${\displaystyle {}_{}}$ ${\$에 대한 타원 곡선이다$.$ The ${\displaystyle \ell }$-torsion group of ${\displaystyle E}$ over ${\displaystyle {\bar {\mathbb {F} }}_{p}}$ is isomorphic to ${\displaystyle \mathbb {Z} /\ell \times \mathbb {Z} /\ell }$ if ${\displaystyle \ell \neq p}$, and to ${\displaystyle \mat$$hbb {Z} /\ell }$ or ${\displaystyle \{0\}}$ if ${\displaystyle \ell =p}$. Hence the degree of ${\displaystyle \psi _{\ell }}$ is equal to either ${\displaystyle {\frac {1}{2}}(l^{2}-1)}$, ${\displaystyle {\frac {1}{2}}(l-1)}$, or 0.

레네 쇼프는 분할 다항식의 ℓ$$ ${\displaystyle \ell}$ 작업 모듈로 $모든{\displaystyle }$ { ${\displaystyle \ell}$ -torion$$ 지점과 동시에 작업할 수 있다고 보았다. 이것은 타원곡선의 점수를 세는 Schoof의 알고리즘에서 많이 사용된다.

참고 항목

• 쇼프의 알고리즘

참조

• A. Enge: 타원 곡선 및 암호화에 대한 응용 프로그램: 소개 1999년 Dordrecht의 Kluwer Academic Publishers.
• N. 코블리츠: 숫자 이론과 암호학, 수학의 대학원 교과 과정. 114번 스프링거-베를라크, 1987. 1994년 2월호
• 뮐러: Die Berechnung der Funktanzahl von 타원리스첸 쿠르베뉴베르 엔드리첸 프리모르펜. 석사 논문. 1991년 Saarbruken, Saarlandes, Universitetht des Saarlandes, Saarbruken
• G. Musicer: Schoof의 $E{\displaystyle }$(${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle$ E$(\mathb {F} _{q}}}}.$http://www-math.mit.edu/~musiker/schoof.pdf에서^{[permanent dead link]} 사용 가능
• Schoof: 유한장 위의 타원곡선과 제곱근 계산 p 수학. 콤프, 44(170):483–494, 1985. http://www.mat.uniroma2.it/~schoof/ctpts.pdf에서 이용 가능
• R. Schoof: 유한 필드 위의 타원 곡선의 점 카운팅. J. 이론. Nombres Bordeaux 7:219–254, 1995. http://www.mat.uniroma2.it/~schoof/ctg.pdf에서 이용 가능
• L. C. Washington: 타원 곡선: 숫자 이론과 암호학. Chapman & Hall/CRC, 2003.
• J. 실버맨: 타원곡선의 산술, 스프링거-버락, GTM 106, 1986.