كثيرات الحدود القسمة

في الرياضيات ، توفر كثيرات الحدود القسمية طريقة لحساب مضاعفات النقاط على المنحنيات الإهليلجية ودراسة الحقول الناتجة عن نقاط الالتواء. وتلعب دورًا محوريًا في دراسة عدّ النقاط على المنحنيات الإهليلجية في خوارزمية شوف .

مجموعة كثيرات الحدود القسمية هي متتالية من كثيرات الحدود في${\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}$

متعددة الحدود${\displaystyle \psi _{n}}$يُطلق عليه اسم متعددة الحدود القسمة من ^الرتبة 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]}$.
• بافتراض نقطة${\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]}$.

يترك${\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)}$أو 0.

لاحظ رينيه شوف أن العمل وفقًا لـ${\displaystyle \ell }$تتيح لك متعددة الحدود من الدرجة الثالثة العمل مع جميع${\displaystyle \ell }$نقاط الالتواء في آن واحد. يُستخدم هذا بكثرة في خوارزمية شوف لحساب النقاط على المنحنيات الإهليلجية.

• خوارزمية شوف

• أ. إنج: المنحنيات الإهليلجية وتطبيقاتها في علم التشفير: مقدمة . دار نشر كلوير الأكاديمية، دوردريخت، 1999.
• ن. كوبليتز: دورة في نظرية الأعداد والتشفير ، نصوص الدراسات العليا في الرياضيات رقم 114، سبرينغر-فيرلاغ، 1987. الطبعة الثانية، 1994
• مولر  : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern . رسالة الماجستير. جامعة سارلاند، ساربروكن، 1991.
• جي. موسيكر: خوارزمية شوف لحساب النقاط على${\displaystyle E(\mathbb {F} _{q})}$متاح على الرابط التالي: https://www-users.cse.umn.edu/~musiker/schoof.pdf
• شوف: المنحنيات الإهليلجية فوق الحقول المنتهية وحساب الجذور التربيعية modulo p . مجلة الرياضيات الحاسوبية، 44(170): 483-494 ، 1985. متاح على الرابط التالي: http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• ر. شوف: عدّ النقاط على المنحنيات الإهليلجية فوق الحقول المنتهية . مجلة الأعداد النظرية بوردو 7: 219-254 ، 1995. متاح على الرابط التالي: http://www.mat.uniroma2.it/~schoof/ctg.pdf
• إل سي واشنطن: المنحنيات الإهليلجية: نظرية الأعداد والتشفير . تشابمان آند هول/سي آر سي، نيويورك، 2003.
• ج. سيلفرمان: حساب المنحنيات الإهليلجية ، سبرينغر-فيرلاغ، GTM 106، 1986.