خوارزمية سيبولا

في نظرية الأعداد الحسابية ، تُعد خوارزمية سيبولا تقنية لحل تطابق من الشكل التالي:

${\displaystyle x^{2}\equiv n{\pmod {p}},}$

أين${\displaystyle x,n\in \mathbf {F} _{p}}$إذن، n هو مربع x ، وحيث${\displaystyle p}$هو عدد أولي فردي . هنا${\displaystyle \mathbf {F} _{p}}$يرمز إلى الحقل المنتهي مع${\displaystyle p}$عناصر ؛${\displaystyle \{0,1,\dots ,p-1\}}$. سميت الخوارزمية على اسم ميشيل سيبولا ، وهو عالم رياضيات إيطالي اكتشفها في عام 1907.

إلى جانب حساب القيم المطلقة للأعداد الأولية، فإن خوارزمية سيبولا قادرة أيضاً على حساب الجذور التربيعية بتردد القوى الأولية. ^{[ 1 ]}

المدخلات:

• ${\displaystyle p}$عدد أولي فردي،
• ${\displaystyle n\in \mathbf {F} _{p}}$وهو مربع.

المخرجات:

• ${\displaystyle x\in \mathbf {F} _{p}}$مرضٍ${\displaystyle x^{2}=n.}$

الخطوة الأولى هي إيجاد${\displaystyle a\in \mathbf {F} _{p}}$بحيث${\displaystyle a^{2}-n}$ليس مربعًا. لا توجد خوارزمية حتمية معروفة لإيجاد مثل هذا الشكل.${\displaystyle a}$ولكن يمكن استخدام طريقة التجربة والخطأ التالية . ببساطة اختر${\displaystyle a}$وبحساب رمز ليجندر${\displaystyle \left({\frac {a^{2}-n}{p}}\right)}$يمكن للمرء أن يرى ما إذا${\displaystyle a}$يحقق الشرط. احتمال أن يكون عشوائيًا${\displaystyle a}$سوف يرضينا${\displaystyle (p-1)/2p}$. مع${\displaystyle p}$هذا كبير بما يكفي، وهذا ما يقارب${\displaystyle 1/2}$^{[ 2 ]} لذلك ، فإن العدد المتوقع للمحاولات قبل إيجاد حل مناسب${\displaystyle a}$يبلغ حوالي 2.

الخطوة الثانية هي حساب قيمة x عن طريق حساب${\displaystyle x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}}$ضمن امتداد الحقل${\displaystyle \mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})}$سيكون هذا المتغير x هو المتغير الذي يحقق المطلوب${\displaystyle x^{2}=n.}$

لو${\displaystyle x^{2}=n}$، ثم${\displaystyle (-x)^{2}=n}$وينطبق هذا أيضاً. وبما أن p عدد فردي،${\displaystyle x\neq -x}$لذلك، كلما تم العثور على حل x ، يكون هناك دائمًا حل ثانٍ، -x .

(ملاحظة: تُعتبر جميع العناصر قبل الخطوة الثانية عنصرًا من عناصر${\displaystyle \mathbf {F} _{13}}$وتُعتبر جميع العناصر في الخطوة الثانية عناصر من${\displaystyle \mathbf {F} _{13^{2}}}$.)

أوجد جميع قيم x التي تحقق${\displaystyle x^{2}=10.}$

قبل تطبيق الخوارزمية، يجب التحقق من${\displaystyle 10}$هو بالفعل مربع في${\displaystyle \mathbf {F} _{13}}$لذلك، رمز ليجاندر${\displaystyle (10|13)}$يجب أن تكون القيمة مساوية لـ 1. ويمكن حساب ذلك باستخدام معيار أويلر :${\textstyle (10|13)\equiv 10^{6}\equiv 1{\pmod {13}}.}$وهذا يؤكد أن العدد 10 مربع، وبالتالي يمكن تطبيق الخوارزمية.

• الخطوة 1: ابحث عن قيمة a بحيث${\displaystyle a^{2}-n}$ليس مربعًا. كما ذُكر، يجب القيام بذلك عن طريق التجربة والخطأ. اختر${\displaystyle a=2}$. ثم${\displaystyle a^{2}-n}$يصبح 7. رمز ليجندر${\displaystyle (7|13)}$يجب أن تكون القيمة -1. ويمكن حساب ذلك باستخدام معيار أويلر:${\textstyle 7^{6}=343^{2}\equiv 5^{2}\equiv 25\equiv -1{\pmod {13}}.}$لذا${\displaystyle a=2}$يُعد خيارًا مناسبًا لـ .
• الخطوة الثانية: الحساب${\displaystyle x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\right)^{7}}$في${\displaystyle \mathbf {F} _{13}({\sqrt {-6}})}$:

${\displaystyle \left(2+{\sqrt {-6}}\right)^{2}=4+4{\sqrt {-6}}-6=-2+4{\sqrt {-6}}}$

${\displaystyle \left(2+{\sqrt {-6}}\right)^{4}=\left(-2+4{\sqrt {-6}}\right)^{2}=-1-3{\sqrt {-6}}}$

${\displaystyle \left(2+{\sqrt {-6}}\right)^{6}=\left(-2+4{\sqrt {-6}}\right)\left(-1-3{\sqrt {-6}}\right)=9+2{\sqrt {-6}}}$

${\displaystyle \left(2+{\sqrt {-6}}\right)^{7}=\left(9+2{\sqrt {-6}}\right)\left(2+{\sqrt {-6}}\right)=6}$

لذا${\displaystyle x=6}$يُعدّ حلاً، وكذلك${\displaystyle x=-6}$. بالفعل،${\textstyle 6^{2}\equiv 10{\pmod {13}}.}$

يتمثل الجزء الأول من البرهان في التحقق من أن${\displaystyle \mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})=\{x+y{\sqrt {a^{2}-n}}:x,y\in \mathbf {F} _{p}\}}$هو بالفعل حقل. ولتبسيط الترميز،${\displaystyle \omega }$يُعرَّف بأنه${\displaystyle {\sqrt {a^{2}-n}}}$. بالطبع،${\displaystyle a^{2}-n}$هو باقي تربيعي، لذا لا يوجد جذر تربيعي في${\displaystyle \mathbf {F} _{p}}$. هذا${\displaystyle \omega }$يمكن اعتبارها تقريبًا مماثلة للعدد المركب i . الحساب الميداني واضح تمامًا. يُعرَّف الجمع على النحو التالي:

${\displaystyle \left(x_{1}+y_{1}\omega \right)+\left(x_{2}+y_{2}\omega \right)=\left(x_{1}+x_{2}\right)+\left(y_{1}+y_{2}\right)\omega }$.

يُعرَّف الضرب أيضاً كالمعتاد. مع الأخذ في الاعتبار أن${\displaystyle \omega ^{2}=a^{2}-n}$يصبح

${\displaystyle \left(x_{1}+y_{1}\omega \right)\left(x_{2}+y_{2}\omega \right)=x_{1}x_{2}+x_{1}y_{2}\omega +y_{1}x_{2}\omega +y_{1}y_{2}\omega ^{2}=\left(x_{1}x_{2}+y_{1}y_{2}\left(a^{2}-n\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega }$.

الآن يجب التحقق من خصائص الحقل. من السهل ملاحظة خصائص الانغلاق تحت عمليتي الجمع والضرب، والتجميعية ، والتبديلية ، والتوزيعية . وذلك لأن الحقل في هذه الحالة${\displaystyle \mathbf {F} _{p^{2}}}$يشبه إلى حد ما مجال الأعداد المركبة (مع${\displaystyle \omega }$(كونه نظيرًا لـ i ). العنصر المحايد الجمعي هو${\displaystyle 0}$أو بشكل أكثر رسمية${\displaystyle 0+0\omega }$: يترك${\displaystyle \alpha \in \mathbf {F} _{p^{2}}}$، ثم

${\displaystyle \alpha +0=(x+y\omega )+(0+0\omega )=(x+0)+(y+0)\omega =x+y\omega =\alpha }$.

العنصر المحايد الضربي هو${\displaystyle 1}$أو بشكل أكثر رسمية${\displaystyle 1+0\omega }$:

${\displaystyle \alpha \cdot 1=(x+y\omega )(1+0\omega )=\left(x\cdot 1+0\cdot y\left(a^{2}-n\right)\right)+(x\cdot 0+1\cdot y)\omega =x+y\omega =\alpha }$.

الشيء الوحيد المتبقي لـ${\displaystyle \mathbf {F} _{p^{2}}}$إن كون الحقل حقلاً يعني وجود معكوسات جمعية ومعكوسات ضربية . ومن السهل ملاحظة أن المعكوس الجمعي لـ${\displaystyle x+y\omega }$يكون${\displaystyle -x-y\omega }$، وهو عنصر من${\displaystyle \mathbf {F} _{p^{2}}}$، لأن${\displaystyle -x,-y\in \mathbf {F} _{p}}$في الواقع، هذه هي العناصر المعكوسة الجمعية لـ x و y . لإثبات أن كل عنصر غير صفري${\displaystyle \alpha }$له معكوس ضربي، اكتبه${\displaystyle \alpha =x_{1}+y_{1}\omega }$و${\displaystyle \alpha ^{-1}=x_{2}+y_{2}\omega }$. بعبارة أخرى،

${\displaystyle (x_{1}+y_{1}\omega )(x_{2}+y_{2}\omega )=\left(x_{1}x_{2}+y_{1}y_{2}\left(a^{2}-n\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega =1}$.

إذن المتساويتان${\displaystyle x_{1}x_{2}+y_{1}y_{2}(a^{2}-n)=1}$و${\displaystyle x_{1}y_{2}+y_{1}x_{2}=0}$يجب أن يستمر. إن حساب التفاصيل يعطي تعبيرات لـ${\displaystyle x_{2}}$و${\displaystyle y_{2}}$، أي

${\displaystyle x_{2}=-y_{1}^{-1}x_{1}\left(y_{1}\left(a^{2}-n\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}}$،

${\displaystyle y_{2}=\left(y_{1}\left(a^{2}-n\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}}$.

العناصر العكسية التي تظهر في تعابير${\displaystyle x_{2}}$و${\displaystyle y_{2}}$موجودة بالفعل، لأن هذه كلها عناصر من${\displaystyle \mathbf {F} _{p}}$وبهذا يكتمل الجزء الأول من البرهان، موضحًا أن${\displaystyle \mathbf {F} _{p^{2}}}$هو حقل.

يُظهر الجزء الثاني والأوسط من البرهان أنه لكل عنصر${\displaystyle x+y\omega \in \mathbf {F} _{p^{2}}:(x+y\omega )^{p}=x-y\omega }$بحسب التعريف،${\displaystyle \omega ^{2}=a^{2}-n}$ليس مربعًا في${\displaystyle \mathbf {F} _{p}}$ثم ينص معيار أويلر على ما يلي:

${\displaystyle \omega ^{p-1}=\left(\omega ^{2}\right)^{\frac {p-1}{2}}=-1}$.

هكذا${\displaystyle \omega ^{p}=-\omega }$هذا، بالإضافة إلى نظرية فيرما الصغرى (التي تنص على أن${\displaystyle x^{p}=x}$للجميع${\displaystyle x\in \mathbf {F} _{p}}$) ومعرفة أنه في المجالات ذات الخاصية p المعادلة${\displaystyle \left(a+b\right)^{p}=a^{p}+b^{p}}$تُظهر العلاقة التي تُسمى أحيانًا حلم الطالب الجديد ، النتيجة المرجوة.

${\displaystyle (x+y\omega )^{p}=x^{p}+y^{p}\omega ^{p}=x-y\omega }$.

أما الجزء الثالث والأخير من البرهان فهو إثبات أنه إذا${\displaystyle x_{0}=\left(a+\omega \right)^{\frac {p+1}{2}}\in \mathbf {F} _{p^{2}}}$، ثم${\displaystyle x_{0}^{2}=n\in \mathbf {F} _{p}}$حساب ​

${\displaystyle x_{0}^{2}=\left(a+\omega \right)^{p+1}=(a+\omega )(a+\omega )^{p}=(a+\omega )(a-\omega )=a^{2}-\omega ^{2}=a^{2}-\left(a^{2}-n\right)=n}$.

لاحظ أن هذه العملية الحسابية تمت في${\displaystyle \mathbf {F} _{p^{2}}}$لذا هذا${\displaystyle x_{0}\in \mathbf {F} _{p^{2}}}$لكن مع نظرية لاغرانج ، التي تنص على أن متعددة الحدود غير الصفرية من الدرجة n لها على الأكثر n جذرًا في أي حقل K ، ومعرفة أن${\displaystyle x^{2}-n}$له جذران في${\displaystyle \mathbf {F} _{p}}$، يجب أن تكون هذه الجذور هي جميع الجذور في${\displaystyle \mathbf {F} _{p^{2}}}$لقد تم توضيح ذلك للتو${\displaystyle x_{0}}$و${\displaystyle -x_{0}}$هي جذور${\displaystyle x^{2}-n}$في${\displaystyle \mathbf {F} _{p^{2}}}$إذن لا بد أن يكون ذلك${\displaystyle x_{0},-x_{0}\in \mathbf {F} _{p}}$[ ^{3 ]​}

بعد إيجاد قيمة مناسبة لـ a ، يكون عدد العمليات المطلوبة للخوارزمية هو${\displaystyle 4m+2k-4}$الضرب،${\displaystyle 4m-2}$المجاميع، حيث m هو عدد الأرقام في التمثيل الثنائي لـ p و k هو عدد الآحاد في هذا التمثيل. لإيجاد قيمة a بالتجربة والخطأ، فإن العدد المتوقع لحسابات رمز ليجندر هو 2. ولكن قد يحالف المرء الحظ من المحاولة الأولى وقد يحتاج إلى أكثر من محاولتين. في هذا المجال${\displaystyle \mathbf {F} _{p^{2}}}$، تتحقق المعادلتان التاليتان

${\displaystyle (x+y\omega )^{2}=\left(x^{2}+y^{2}\omega ^{2}\right)+\left(\left(x+y\right)^{2}-x^{2}-y^{2}\right)\omega ,}$

أين${\displaystyle \omega ^{2}=a^{2}-n}$معروف مسبقًا. تتطلب هذه العملية الحسابية 4 عمليات ضرب و4 عمليات جمع.

${\displaystyle \left(x+y\omega \right)^{2}\left(a+\omega \right)=\left(ad^{2}-b\left(x+d\right)\right)+\left(d^{2}-by\right)\omega ,}$

أين${\displaystyle d=(x+ya)}$و${\displaystyle b=ny}$تتطلب هذه العملية 6 عمليات ضرب و 4 عمليات جمع.

بافتراض أن${\displaystyle p\equiv 1{\pmod {4}},}$(في هذه الحالة)${\displaystyle p\equiv 3{\pmod {4}}}$، الحساب المباشر${\displaystyle x\equiv \pm n^{\frac {p+1}{4}}}$(أسرع بكثير) التعبير الثنائي لـ${\displaystyle (p+1)/2}$لديه${\displaystyle m-1}$الأرقام، منها k من الآحاد. لذا لحساب a${\displaystyle (p+1)/2}$قوة${\displaystyle \left(a+\omega \right)}$يجب استخدام الصيغة الأولى${\displaystyle n-k-1}$مرتين والثانية${\displaystyle k-1}$مرات.

لهذا السبب، تكون خوارزمية سيبولا أفضل من خوارزمية تونيللي-شانكس إذا وفقط إذا${\displaystyle S(S-1)>8m+20}$، مع${\displaystyle 2^{S}}$كونها أعلى قوة للعدد 2 التي تقسم${\displaystyle p-1}$[ ^{4 ]​}

وفقًا لكتاب ديكسون "تاريخ الأعداد"، فإن صيغة سيبولا التالية ستجد الجذور التربيعية بتردد قوى الأعداد الأولية: ^{[ 5 ] [ 6 ]}

${\displaystyle 2^{-1}q^{t}((k+{\sqrt {k^{2}-q}})^{s}+(k-{\sqrt {k^{2}-q}})^{s}){\bmod {p^{\lambda }}}}$

أين${\displaystyle t=(p^{\lambda }-2p^{\lambda -1}+1)/2}$و${\displaystyle s=p^{\lambda -1}(p+1)/2}$

أين${\displaystyle q=10}$،${\displaystyle k=2}$كما هو الحال في مثال هذه المقالة

بالنظر إلى المثال الوارد في مقالة ويكي، يمكننا أن نرى أن هذه الصيغة أعلاه تأخذ بالفعل الجذور التربيعية بتردد القوى الأولية.

مثل

${\displaystyle {\sqrt {10}}{\bmod {13^{3}}}\equiv 1046}$

الآن أوجد قيمة${\displaystyle 2^{-1}q^{t}}$عبر:

${\displaystyle 2^{-1}10^{(13^{3}-2\cdot 13^{2}+1)/2}{\bmod {13^{3}}}\equiv 1086}$

الآن قم بإنشاء${\displaystyle (2+{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}}$و${\displaystyle (2-{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}}$ (انظر هنا للحصول على كود Mathematica الذي يوضح هذه العملية الحسابية أعلاه، مع الأخذ في الاعتبار أن شيئًا قريبًا من الحساب النمطي المعقد يحدث هنا)

كما:

${\displaystyle (2+{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}\equiv 1540}$ و${\displaystyle (2-{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}\equiv 1540}$

والمعادلة النهائية هي:

${\displaystyle 1086(1540+1540){\bmod {13^{3}}}\equiv 1046}$ وهذا هو الجواب.

• إي. باخ ، جيه أو شاليت، نظرية الأعداد الخوارزمية: خوارزميات فعالة، مطبعة معهد ماساتشوستس للتكنولوجيا، (1996)