Dělicí polynomy - Division polynomials

v matematika the dělící polynomy poskytnout způsob, jak vypočítat násobky bodů na eliptické křivky a studovat pole generovaná torzními body. Hrají ústřední roli ve studiu počítání bodů na eliptických křivkách v Schoofův algoritmus.

Definice

Sada dělících polynomů je posloupností polynomy v ${displaystyle mathbb {Z} [x, y, A, B]}$ s ${displaystyle x, y, A, B}$ volné proměnné, které jsou rekurzivně definovány:

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

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

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

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

Polynom ${displaystyle psi _ {n}}$ se nazývá n^th dělení polynomu.

Vlastnosti

• V praxi se jedna nastaví ${displaystyle y ^ {2} = x ^ {3} + Axe + B}$, a pak ${displaystyle psi _ {2m + 1} v mathbb {Z} [x, A, B]}$ a ${displaystyle psi _ {2m} ve 2ymathbb {Z} [x, A, B]}$.
• Dělicí polynomy tvoří druhové sekvence eliptické dělitelnosti přes prsten ${displaystyle mathbb {Q} [x, y, A, B] / (y ^ {2} -x ^ {3} -Ax-B)}$.
• Pokud eliptická křivka ${displaystyle E}$ je uveden v Weierstrassova forma ${displaystyle y ^ {2} = x ^ {3} + Axe + B}$ přes nějaké pole ${displaystyle K}$, tj. ${displaystyle A, Bin K}$, lze použít tyto hodnoty ${displaystyle A, B}$ a zvažte dělení polynomů v souřadnicový kruh z ${displaystyle E}$. Kořeny ${displaystyle psi _ {2n + 1}}$ jsou ${displaystyle x}$- souřadnice bodů ${displaystyle E [2n + 1] setminus {O}}$, kde ${displaystyle E [2n + 1]}$ je ${displaystyle (2n + 1) ^ {ext {th}}}$ torzní podskupina z ${displaystyle E}$. Podobně kořeny ${displaystyle psi _ {2n} / rok}$ jsou ${displaystyle x}$- souřadnice bodů ${displaystyle E [2n] setminus E [2]}$.
• Daný bod ${displaystyle P = (x_ {P}, y_ {P})}$ na eliptické křivce ${displaystyle E: y ^ {2} = x ^ {3} + Axe + B}$ přes nějaké pole ${displaystyle K}$, můžeme vyjádřit souřadnice n^th násobek ${displaystyle P}$ z hlediska dělení polynomů:

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

kde ${displaystyle phi _ {n}}$ a ${displaystyle omega _ {n}}$ jsou definovány:

${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}}.}$

Využití vztahu mezi ${displaystyle psi _ {2m}}$ a ${displaystyle psi _ {2m + 1}}$, spolu s rovnicí křivky, funkce ${displaystyle psi _ {n} ^ {2}}$ , ${displaystyle {frac {psi _ {2n}} {y}}, psi _ {2n + 1}}$, ${displaystyle phi _ {n}}$ jsou všichni v ${displaystyle K [x]}$.

Nechat ${displaystyle p> 3}$ být připravený a nechat ${displaystyle E: y ^ {2} = x ^ {3} + Axe + B}$ být eliptická křivka přes konečné pole ${displaystyle mathbb {F} _ {p}}$, tj., ${displaystyle A, Bin mathbb {F} _ {p}}$. The ${displaystyle ell}$-toriální skupina ${displaystyle E}$ přes ${displaystyle {ar {mathbb {F}}} _ {p}}$ je izomorfní na ${displaystyle mathbb {Z} / ell imes mathbb {Z} / ell}$ -li ${displaystyle ell eq p}$a do ${displaystyle mathbb {Z} / ell}$ nebo ${displaystyle {0}}$ -li ${displaystyle ell = p}$. Proto stupeň ${displaystyle psi _ {ell}}$ se rovná buď ${displaystyle {frac {1} {2}} (l ^ {2} -1)}$, ${displaystyle {frac {1} {2}} (l-1)}$nebo 0.

René Schoof poznamenal, že pracovní modulo ${displaystyle ell}$th divizní polynom umožňuje člověku pracovat se všemi ${displaystyle ell}$- torzní body současně. Toto se velmi používá v Schoofův algoritmus pro počítání bodů na eliptických křivkách.

Viz také

• Schoofův algoritmus

Reference

• A. Enge: Eliptické křivky a jejich aplikace v kryptografii: Úvod. Kluwer Academic Publishers, Dordrecht, 1999.
• N. Koblitz: Kurz teorie čísel a kryptografie, Postgraduální texty v matematice. No. 114, Springer-Verlag, 1987. Druhé vydání, 1994
• Müller: Die Berechnung der Punktanzahl von elliptischen kurvenüber endlichen Primkörpern. Diplomová práce. Universität des Saarlandes, Saarbrücken, 1991.
• G. Musiker: Schoofův algoritmus pro počítání bodů ${displaystyle E (mathbb {F} _ {q})}$. Dostupné v http://www-math.mit.edu/~musiker/schoof.pdf^{[trvalý mrtvý odkaz ]}
• Schoof: Eliptické křivky nad konečnými poli a výpočet čtvercových kořenů mod str. Matematika. Comp., 44 (170): 483–494, 1985. Dostupné na http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• R. Schoof: Počítání bodů na eliptických křivkách přes konečná pole. J. Theor. Nombres Bordeaux 7: 219–254, 1995. Dostupné na http://www.mat.uniroma2.it/~schoof/ctg.pdf
• L. C. Washington: Eliptické křivky: teorie čísel a kryptografie. Chapman & Hall / CRC, New York, 2003.
• J. Silverman: Aritmetika eliptických křivekSpringer-Verlag, GTM 106, 1986.