خوارزمية شوف

خوارزمية شوف هي خوارزمية فعّالة لحساب النقاط على المنحنيات الإهليلجية في الحقول المنتهية . وتُستخدم هذه الخوارزمية في تشفير المنحنيات الإهليلجية، حيث يُعدّ معرفة عدد النقاط أمرًا بالغ الأهمية لتقييم صعوبة حلّ مسألة اللوغاريتم المنفصل في مجموعة النقاط على المنحنى الإهليلجي.

نُشرت الخوارزمية بواسطة رينيه شوف عام 1985، وشكّلت إنجازًا نظريًا هامًا، إذ كانت أول خوارزمية حتمية متعددة الحدود لحساب النقاط على المنحنيات الإهليلجية . قبل خوارزمية شوف، كانت طرق حساب النقاط على المنحنيات الإهليلجية، مثل خوارزمية الخطوة البسيطة وخوارزمية الخطوة العملاقة ، في معظمها شاقة وتستغرق وقتًا طويلًا جدًا.

تشرح هذه المقالة نهج شوف، مع التركيز على الأفكار الرياضية التي يقوم عليها هيكل الخوارزمية.

يترك${\displaystyle E}$ليكن منحنى إهليلجي معرفًا على الحقل المنتهي${\displaystyle \mathbb {F} _{q}}$، أين${\displaystyle q=p^{n}}$ل${\displaystyle p}$رئيس الوزراء و${\displaystyle n}$عدد صحيح${\displaystyle \geq 1}$. على مجال من الخصائص${\displaystyle \neq 2,3}$يمكن تمثيل المنحنى الإهليلجي بمعادلة فايرشتراس (المختصرة).

${\displaystyle y^{2}=x^{3}+Ax+B}$

مع${\displaystyle A,B\in \mathbb {F} _{q}}$مجموعة النقاط المعرفة على${\displaystyle \mathbb {F} _{q}}$يتكون من الحلول${\displaystyle (a,b)\in \mathbb {F} _{q}^{2}}$تحقق معادلة المنحنى ونقطة عند اللانهاية${\displaystyle O}$باستخدام قانون المجموعة على المنحنيات الإهليلجية المقيد بهذه المجموعة، يمكن للمرء أن يرى أن هذه المجموعة${\displaystyle E(\mathbb {F} _{q})}$يشكل مجموعة أبيلية ، مع${\displaystyle O}$يعمل كعنصر الصفر. لحساب عدد النقاط على منحنى إهليلجي، نحسب عدد عناصر${\displaystyle E(\mathbb {F} _{q})}$نهج شوف في حساب عدد العناصر${\displaystyle \#E(\mathbb {F} _{q})}$يستخدم نظرية هاس على المنحنيات الإهليلجية بالإضافة إلى نظرية الباقي الصينية وكثيرات الحدود القسمة .

تنص نظرية هاس على أنه إذا${\displaystyle E/\mathbb {F} _{q}}$هو منحنى إهليلجي فوق الحقل المنتهي${\displaystyle \mathbb {F} _{q}}$، ثم${\displaystyle \#E(\mathbb {F} _{q})}$يرضي

${\displaystyle \mid q+1-\#E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q}}.}$

هذه النتيجة القوية، التي قدمها هاس في عام 1934، تبسط مشكلتنا عن طريق تضييق نطاقها${\displaystyle \#E(\mathbb {F} _{q})}$إلى مجموعة محدودة (وإن كانت كبيرة) من الاحتمالات. تعريف${\displaystyle t}$يكون${\displaystyle q+1-\#E(\mathbb {F} _{q})}$وباستخدام هذه النتيجة، أصبح لدينا الآن أن حساب قيمة${\displaystyle t}$modulo${\displaystyle N}$أين${\displaystyle N>4{\sqrt {q}}}$، يكفي لتحديد${\displaystyle t}$وبالتالي${\displaystyle \#E(\mathbb {F} _{q})}$على الرغم من عدم وجود طريقة فعالة للحساب${\displaystyle t{\pmod {N}}}$مباشرة للجمهور${\displaystyle N}$، من الممكن حساب${\displaystyle t{\pmod {l}}}$ل${\displaystyle l}$عدد أولي صغير، بكفاءة عالية. نختار${\displaystyle S=\{l_{1},l_{2},...,l_{r}\}}$أن تكون مجموعة من الأعداد الأولية المتميزة بحيث${\displaystyle \prod l_{i}=N>4{\sqrt {q}}}$. منح${\displaystyle t{\pmod {l_{i}}}}$للجميع${\displaystyle l_{i}\in S}$تسمح لنا نظرية الباقي الصينية بحساب${\displaystyle t{\pmod {N}}}$.

من أجل الحساب${\displaystyle t{\pmod {l}}}$لـ${\displaystyle l\neq p}$، نستفيد من نظرية التشكل الداخلي لفروبينيوس${\displaystyle \phi }$وكثيرات الحدود القسمية . لاحظ أنه عند النظر إلى الأعداد الأولية${\displaystyle l\neq p}$لا يُعدّ ذلك خسارة، إذ يُمكننا دائمًا اختيار عدد أولي أكبر ليحلّ محلّه لضمان أن يكون الناتج كبيرًا بما يكفي. على أي حال، تُستخدم خوارزمية شوف في أغلب الأحيان لمعالجة هذه الحالة.${\displaystyle q=p}$بما أن هناك ما يسمى أكثر كفاءة${\displaystyle p}$خوارزميات adic للحقول ذات الخصائص الصغيرة.

بالنظر إلى المنحنى الإهليلجي${\displaystyle E}$تم تعريفها على${\displaystyle \mathbb {F} _{q}}$نأخذ في الاعتبار النقاط المتعلقة بـ${\displaystyle E}$زيادة${\displaystyle {\bar {\mathbb {F} }}_{q}}$، الإغلاق الجبري لـ${\displaystyle \mathbb {F} _{q}}$أي أننا نسمح بالنقاط ذات الإحداثيات في${\displaystyle {\bar {\mathbb {F} }}_{q}}$. التشكل الداخلي لفروبينيوس لـ${\displaystyle {\bar {\mathbb {F} }}_{q}}$زيادة${\displaystyle \mathbb {F} _{q}}$يمتد إلى المنحنى الإهليلجي بواسطة${\displaystyle \phi$ :(x,y)\mapsto (x^{q},y^{q})} .

هذه الخريطة هي الهوية على${\displaystyle E(\mathbb {F} _{q})}$ويمكن للمرء أن يمتد إلى نقطة اللانهاية.${\displaystyle O}$مما يجعلها تشاكلاً جماعياً من${\displaystyle E({\bar {\mathbb {F} }}_{q})}$لنفسه.

يحقق تحويل فروبينيوس الداخلي متعددة حدود من الدرجة الثانية مرتبطة بعدد عناصر${\displaystyle E(\mathbb {F} _{q})}$وفقًا للنظرية التالية:

النظرية: التشاكل الداخلي لفروبينيوس المعطى بواسطة${\displaystyle \phi }$يحقق المعادلة المميزة

${\displaystyle \phi ^{2}-t\phi +q=0,}$أين${\displaystyle t=q+1-\#E(\mathbb {F} _{q})}$

وهكذا لدينا للجميع${\displaystyle P=(x,y)\in E}$الذي - التي${\displaystyle (x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})}$حيث تشير علامة الجمع (+) إلى الجمع على المنحنى الإهليلجي و${\displaystyle q(x,y)}$و${\displaystyle t(x^{q},y^{q})}$ يرمز إلى الضرب القياسي لـ${\displaystyle (x,y)}$بواسطة${\displaystyle q}$و من${\displaystyle (x^{q},y^{q})}$بواسطة${\displaystyle t}$.

يمكن للمرء أن يحاول حساب هذه النقاط بشكل رمزي${\displaystyle (x^{q^{2}},y^{q^{2}})}$،${\displaystyle (x^{q},y^{q})}$و${\displaystyle q(x,y)}$كدوال في حلقة الإحداثيات${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)}$ل${\displaystyle E}$ ثم ابحث عن قيمة لـ${\displaystyle t}$وهذا يحقق المعادلة. ومع ذلك، تصبح الدرجات كبيرة جدًا، وهذا النهج غير عملي.

كانت فكرة شوف هي إجراء هذه الحسابات مقتصرة على نقاط الترتيب${\displaystyle l}$بالنسبة للعديد من الأعداد الأولية الصغيرة${\displaystyle l}$. إصلاح عدد أولي فردي${\displaystyle l}$ننتقل الآن إلى حل مشكلة تحديد${\displaystyle t_{l}}$، كما هو مُعرَّف${\displaystyle t{\pmod {l}}}$، لعدد أولي معين${\displaystyle l\neq 2,p}$إذا كانت هناك نقطة${\displaystyle (x,y)}$موجود في${\displaystyle l}$- مجموعة فرعية للالتواء${\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q}}})\mid lP=O\}}$، ثم${\displaystyle qP={\bar {q}}P}$أين${\displaystyle {\bar {q}}}$هو العدد الصحيح الوحيد الذي يحقق ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$و${\displaystyle \mid {\bar {q}}\mid <l/2}$. لاحظ أن${\displaystyle \phi (O)=O}$وذلك لأي عدد صحيح${\displaystyle r}$لدينا${\displaystyle r\phi (P)=\phi (rP)}$. هكذا${\displaystyle \phi (P)}$سيكون له نفس الترتيب مثل${\displaystyle P}$وهكذا بالنسبة لـ${\displaystyle (x,y)}$ينتمي إلى${\displaystyle E[l]}$لدينا أيضًا${\displaystyle t(x^{q},y^{q})={\bar {t}}(x^{q},y^{q})}$لو${\displaystyle t\equiv {\bar {t}}{\pmod {l}}}$وبالتالي، فقد اختزلنا مشكلتنا إلى حل المعادلة

${\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{q},y^{q}),}$

أين${\displaystyle {\bar {t}}}$و${\displaystyle {\bar {q}}}$لها قيم صحيحة في${\displaystyle [-(l-1)/2,(l-1)/2]}$.

كثير الحدود القسمي من الرتبة l هو الذي تكون جذوره هي إحداثيات x لنقاط من الرتبة l . وبالتالي، لتقييد حساب${\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$الوصول إلى نقاط الالتواء من الرتبة l يعني حساب هذه التعبيرات كدوال في حلقة إحداثيات E وباقي القسمة على متعدد الحدود من الرتبة l . أي أننا نعمل في${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$وهذا يعني على وجه الخصوص أن درجة X و Y المحددة عبر${\displaystyle (X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$لا يتجاوز 1 في y ولا يتجاوز${\displaystyle (l^{2}-3)/2}$ في x .

الضرب القياسي${\displaystyle {\bar {q}}(x,y)}$يمكن القيام بذلك إما عن طريق طرق المضاعفة والجمع أو باستخدام${\displaystyle {\bar {q}}}$متعددة الحدود من الدرجة n. ويعطي النهج الأخير ما يلي:

${\displaystyle {\bar {q}}(x,y)=(x_{\bar {q}},y_{\bar {q}})=\left(x-{\frac {\psi _{{\bar {q}}-1}\psi _{{\bar {q}}+1}}{\psi _{\bar {q}}^{2}}},{\frac {\psi _{2{\bar {q}}}}{2\psi _{\bar {q}}^{4}}}\right)}$

أين${\displaystyle \psi _{n}}$هي كثيرة الحدود من الدرجة n . لاحظ أن ${\displaystyle y_{\bar {q}}/y}$هي دالة في x فقط ونرمز لها بـ${\displaystyle \theta (x)}$.

يجب أن نقسم المشكلة إلى حالتين: الحالة التي${\displaystyle (x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)}$والحالة التي ${\displaystyle (x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)}$لاحظ أن هذه المتساويات يتم التحقق منها بتردد صفري.${\displaystyle \psi _{l}}$.

 مدخل: 1. منحنى إهليلجي${\displaystyle E=y^{2}-x^{3}-Ax-B}$. 2. عدد صحيح q لحقل منتهٍ${\displaystyle F_{q}}$مع${\displaystyle q=p^{b},b\geq 1}$. الناتج: عدد نقاط E على${\displaystyle F_{q}}$. اختر مجموعة من الأعداد الأولية الفردية S لا تحتوي على p بحيث${\displaystyle N=\prod _{l\in S}l>4{\sqrt {q}}.}$يضع${\displaystyle t_{2}=0}$لو${\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}$، آخر${\displaystyle t_{2}=1}$احسب كثيرة الحدود القسمية${\displaystyle \psi _{l}}$. تُجرى جميع العمليات الحسابية في الحلقة أدناه داخل الحلقة${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).}$ل${\displaystyle l\in S}$افعل : دع${\displaystyle {\bar {q}}}$ليكن العدد الصحيح الوحيد الذي يحقق ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$و${\displaystyle \mid {\bar {q}}\mid <l/2}$حساب​${\displaystyle (x^{q},y^{q})}$،${\displaystyle (x^{q^{2}},y^{q^{2}})}$و${\displaystyle (x_{\bar {q}},y_{\bar {q}})}$. لو${\displaystyle x^{q^{2}}\neq x_{\bar {q}}}$ثم احسب${\displaystyle (X,Y)}$. ل${\displaystyle 1\leq {\bar {t}}\leq (l-1)/2}$نفّذ : إذا${\displaystyle X=x_{\bar {t}}^{q}}$ثم إذا${\displaystyle Y=y_{\bar {t}}^{q}}$ثم${\displaystyle t_{l}={\bar {t}}}$؛ آخر${\displaystyle t_{l}=-{\bar {t}}}$وإلا ، إذا كان q مربعًا بتردد l ، فاحسب w باستخدام${\displaystyle q\equiv w^{2}{\pmod {l}}}$حساب${\displaystyle w(x^{q},y^{q})}$لو${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})}$ثم${\displaystyle t_{l}=2w}$وإلا إذا${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})}$ثم${\displaystyle t_{l}=-2w}$آخر${\displaystyle t_{l}=0}$آخر${\displaystyle t_{l}=0}$ استخدم نظرية الباقي الصينية لحساب t modulo N من المعادلات${\displaystyle t\equiv t_{l}{\pmod {l}}}$، أين${\displaystyle l\in S}$. الناتج${\displaystyle q+1-t}$.

تُجرى معظم العمليات الحسابية من خلال تقييم${\displaystyle \phi (P)}$و${\displaystyle \phi ^{2}(P)}$لكل عدد أولي${\displaystyle l}$أي الحوسبة${\displaystyle x^{q}}$،${\displaystyle y^{q}}$،${\displaystyle x^{q^{2}}}$،${\displaystyle y^{q^{2}}}$لكل عدد أولي${\displaystyle l}$وهذا يتضمن عملية الأس في الحلقة${\displaystyle R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$ويتطلب${\displaystyle O(\log q)}$الضرب. بما أن درجة${\displaystyle \psi _{l}}$يكون${\displaystyle {\frac {l^{2}-1}{2}}}$كل عنصر في الحلقة هو متعدد حدود من الدرجة${\displaystyle O(l^{2})}$بحسب نظرية الأعداد الأولية ، يوجد حوالي${\displaystyle O(\log q)}$أحجام أولية${\displaystyle O(\log q)}$مع الأخذ في الاعتبار ذلك${\displaystyle l}$يكون${\displaystyle O(\log q)}$ونحصل على ذلك${\displaystyle O(l^{2})=O(\log ^{2}q)}$وهكذا، فإن كل عملية ضرب في الحلقة${\displaystyle R}$يتطلب${\displaystyle O(\log ^{4}q)}$الضرب في${\displaystyle \mathbb {F} _{q}}$وهذا بدوره يتطلب${\displaystyle O(\log ^{2}q)}$عمليات البت. إجمالاً، عدد عمليات البت لكل عدد أولي${\displaystyle l}$يكون${\displaystyle O(\log ^{7}q)}$بالنظر إلى أن هذه العملية الحسابية يجب إجراؤها لكل من${\displaystyle O(\log q)}$الأعداد الأولية، وبالتالي فإن التعقيد الكلي لخوارزمية شوف هو${\displaystyle O(\log ^{8}q)}$يؤدي استخدام العمليات الحسابية السريعة على كثيرات الحدود والأعداد الصحيحة إلى تقليل ذلك إلى${\displaystyle {\tilde {O}}(\log ^{5}q)}$.

في تسعينيات القرن العشرين، قام نعوم إلكيس ، وتبعه إيه أو إل أتكين ، بتطوير تحسينات على خوارزمية شوف الأساسية عن طريق تقييد مجموعة الأعداد الأولية.${\displaystyle S=\{l_{1},\ldots ,l_{s}\}}$تم اعتبارها سابقًا أعدادًا أولية من نوع معين. وقد أُطلق عليها اسم أعداد إلكيز الأولية وأعداد أتكين الأولية على التوالي. العدد الأولي${\displaystyle l}$يُطلق عليه اسم عدد إلكيز الأولي إذا كانت معادلته المميزة:${\displaystyle \phi ^{2}-t\phi +q=0}$ينقسم على${\displaystyle \mathbb {F} _{l}}$بينما العدد الأولي أتكين هو عدد أولي ليس عددًا أوليًا إلكيز. أوضح أتكين كيفية دمج المعلومات المستقاة من أعداد أتكين الأولية مع المعلومات المستقاة من أعداد إلكيز الأولية لإنتاج خوارزمية فعالة، عُرفت فيما بعد باسم خوارزمية شوف-إلكيز-أتكين . تتمثل المشكلة الأولى التي يجب معالجتها في تحديد ما إذا كان عدد أولي معين هو عدد إلكيز أو عدد أتكين. وللقيام بذلك، نستخدم كثيرات الحدود النمطية، المستمدة من دراسة الأشكال النمطية وتفسير المنحنيات الإهليلجية على الأعداد المركبة كشبكات. بمجرد تحديد الحالة، بدلاً من استخدام كثيرات حدود القسمة ، يمكننا العمل بكثيرة حدود ذات درجة أقل من كثير حدود القسمة المقابل.${\displaystyle O(l)}$بدلاً من${\displaystyle O(l^{2})}$لتحقيق كفاءة التنفيذ، تُستخدم خوارزميات احتمالية لإيجاد الجذور، مما يجعل هذه الخوارزمية أشبه بخوارزمية لاس فيغاس وليست خوارزمية حتمية. بافتراض أن نصف الأعداد الأولية تقريبًا حتى 10 ...${\displaystyle O(\log q)}$إذا كانت الحدود أعدادًا أولية من نوع Elkies، فإن هذا ينتج عنه خوارزمية أكثر كفاءة من خوارزمية Schoof، مع وقت تشغيل متوقع قدره${\displaystyle O(\log ^{6}q)}$باستخدام الحساب البسيط، و${\displaystyle {\tilde {O}}(\log ^{4}q)}$باستخدام العمليات الحسابية السريعة. على الرغم من أن هذا الافتراض الاستدلالي معروف بأنه ينطبق على معظم المنحنيات الإهليلجية، إلا أنه ليس من المعروف أنه ينطبق في كل حالة، حتى في ظل فرضية إعادة التركيب المعممة .

قام مايك سكوت بتنفيذ العديد من الخوارزميات بلغة C++ . هذه التطبيقات مجانية (بدون شروط أو قيود)، وتستخدم مكتبة MIRACL الموزعة بموجب رخصة AGPLv3 .

• تطبيق خوارزمية شوف لـ${\displaystyle E(\mathbb {F} _{p})}$مع برايم${\displaystyle p}$.
• تطبيق خوارزمية شوف لـ${\displaystyle E(\mathbb {F} _{2^{m}})}$.

• التشفير باستخدام المنحنى الإهليلجي
• عد النقاط على المنحنيات الإهليلجية
• كثيرات الحدود القسمة
• التماثل الداخلي لفروبينيوس

• ر. شوف: المنحنيات الإهليلجية فوق الحقول المنتهية وحساب الجذور التربيعية 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
• جي. موسيكر: خوارزمية شوف لحساب النقاط على${\displaystyle E(\mathbb {F} _{q})}$متاح على الرابط التالي: http://www.math.umn.edu/~musiker/schoof.pdf
• V. Müller  : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. رسالة الماجستير. جامعة سارلاند، ساربروكن، 1991. متاح على http://lecturer.ukdw.ac.id/vmueller/publications.php أرشفة 2020-07-28 في آلة Wayback.
• أ. إنج: المنحنيات الإهليلجية وتطبيقاتها في علم التشفير: مقدمة. دار نشر كلوير الأكاديمية، دوردريخت، 1999.
• إل سي واشنطن: المنحنيات الإهليلجية: نظرية الأعداد والتشفير. تشابمان آند هول/سي آر سي، نيويورك، 2003.
• ن. كوبليتز: دورة في نظرية الأعداد والتشفير، نصوص الدراسات العليا في الرياضيات رقم 114، سبرينغر-فيرلاغ، 1987. الطبعة الثانية، 1994