خوارزمية بوكلينجتون

يفصل بوكلينجتون 3 حالات مختلفة لـ p :

الحالة الأولى، إذا${\displaystyle p=4m+3}$، مع${\displaystyle m\in \mathbb {N} }$الحل هو${\displaystyle x\equiv \pm a^{m+1}}$.

الحالة الثانية، إذا${\displaystyle p=8m+5}$، مع${\displaystyle m\in \mathbb {N} }$و

1. ${\displaystyle a^{2m+1}\equiv 1}$الحل هو${\displaystyle x\equiv \pm a^{m+1}}$.
2. ${\displaystyle a^{2m+1}\equiv -1}$، 2 هو باقي (تربيعي) لذا${\displaystyle 4^{2m+1}\equiv -1}$وهذا يعني أن${\displaystyle (4a)^{2m+1}\equiv 1}$لذا${\displaystyle y\equiv \pm (4a)^{m+1}}$هو حل لـ${\displaystyle y^{2}\equiv 4a}$. لذلك${\displaystyle x\equiv \pm y/2}$أو إذا كانت قيمة y فردية،${\displaystyle x\equiv \pm (p+y)/2}$.

الحالة الثالثة، إذا${\displaystyle p=8m+1}$، يضع${\displaystyle D\equiv -a}$وبالتالي تصبح المعادلة المطلوب حلها${\displaystyle x^{2}+D\equiv 0}$والآن، ابحث عن ذلك بالتجربة والخطأ.${\displaystyle t_{1}}$و${\displaystyle u_{1}}$لهذا السبب.${\displaystyle N=t_{1}^{2}-Du_{1}^{2}}$هو باقي تربيعي. علاوة على ذلك، ليكن

${\displaystyle t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}},\qquad u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}}$.

تسري الآن المتساويات التالية:

${\displaystyle t_{m+n}=t_{m}t_{n}+Du_{m}u_{n},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad t_{n}^{2}-Du_{n}^{2}=N^{n}}$.

بافتراض أن p على الشكل${\displaystyle 4m+1}$(وهذا صحيح إذا كان p على الشكل${\displaystyle 8m+1}$، D هو متبقي تربيعي و${\displaystyle t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}}$والآن المعادلات

${\displaystyle t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}\quad {\mbox{and}}\quad u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}}$

قدّم حلاً${\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0}$.

يترك${\displaystyle p-1=2r}$. ثم${\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}}$وهذا يعني إما${\displaystyle t_{r}}$أو${\displaystyle u_{r}}$يقبل القسمة على p . إذا كان${\displaystyle u_{r}}$، يضع${\displaystyle r=2s}$واتبع نفس النهج مع${\displaystyle 0\equiv 2t_{s}u_{s}}$ليس كل${\displaystyle u_{i}}$يقبل القسمة على p ، لأن${\displaystyle u_{1}}$ليس كذلك. القضية${\displaystyle u_{m}\equiv 0}$من المستحيل أن يكون عدد m فرديًا، لأن${\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}}$وهذا يعني أن${\displaystyle t_{m}^{2}}$يتطابق مع باقي تربيعي غير موجود، وهذا تناقض. لذا تتوقف هذه الحلقة عندما${\displaystyle t_{l}\equiv 0}$بالنسبة لقيمة معينة لـ l . وهذا يعطي${\displaystyle -Du_{l}^{2}\equiv N^{l}}$ولأن${\displaystyle -D}$إذا كان الباقي من الدرجة الثانية، فيجب أن يكون l زوجيًا. ضع${\displaystyle l=2k}$. ثم${\displaystyle 0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}}$إذن، الحل هو${\displaystyle x^{2}+D\equiv 0}$يتم الحصول عليها عن طريق حل التطابق الخطي${\displaystyle u_{k}x\equiv \pm t_{k}}$.

${\displaystyle x^{2}\equiv 43{\pmod {47}}.}$

هذه هي الحالة الأولى، وفقًا للخوارزمية، ${\displaystyle x\equiv 43^{(47+1)/2}=43^{12}\equiv 2}$لكن بعد ذلك${\displaystyle x^{2}=2^{2}=4}$ليس 43، لذا لا ينبغي تطبيق الخوارزمية على الإطلاق. والسبب في عدم إمكانية تطبيق الخوارزمية هو أن a=43 هو باقي تربيعي غير موجب لـ p=47.

حل التطابق

${\displaystyle x^{2}\equiv 18{\pmod {23}}.}$

المعامل هو 23. هذا هو${\displaystyle 23=4\cdot 5+3}$، لذا${\displaystyle m=5}$ينبغي أن يكون الحل${\displaystyle x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}}$وهذا صحيح بالفعل:${\displaystyle (\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}}$.

حل التطابق

${\displaystyle x^{2}\equiv 10{\pmod {13}}.}$

المعامل هو 13. هذا هو${\displaystyle 13=8\cdot 1+5}$، لذا${\displaystyle m=1}$جارٍ التحقق الآن${\displaystyle 10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}}$إذن الحل هو${\displaystyle x\equiv \pm y/2\equiv \pm (4a)^{2}/2\equiv \pm 800\equiv \pm 7{\pmod {13}}}$هذا صحيح بالفعل:${\displaystyle (\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}}$.

حل التطابق${\displaystyle x^{2}\equiv 13{\pmod {17}}}$لذلك، اكتب${\displaystyle x^{2}-13=0}$أولاً، ابحث عن${\displaystyle t_{1}}$و${\displaystyle u_{1}}$بحيث${\displaystyle t_{1}^{2}+13u_{1}^{2}}$هو باقي تربيعي. خذ على سبيل المثال${\displaystyle t_{1}=3,u_{1}=1}$والآن ابحث${\displaystyle t_{8}}$،${\displaystyle u_{8}}$عن طريق الحساب

${\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},}$

${\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.}$

وبالمثل${\displaystyle t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}}$بحيث${\displaystyle t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.}$

منذ${\displaystyle t_{8}=0}$المعادلة${\displaystyle 0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}}$مما يؤدي إلى حل المعادلة${\displaystyle 3x\equiv \pm 7{\pmod {17}}}$هذا له حل${\displaystyle x\equiv \pm 8{\pmod {17}}}$. بالفعل،${\displaystyle (\pm 8)^{2}=64\equiv 13{\pmod {17}}}$.