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

يترك${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\cdots (x-\lambda _{n})}$إن إيجاد جميع جذور هذه المعادلة متعددة الحدود يكافئ إيجاد تحليلها إلى عوامل خطية. ولإيجاد هذا التحليل، يكفي تقسيم المعادلة إلى أي قاسمين غير تافهين وتحليلهما بشكل متكرر. وللقيام بذلك، لننظر إلى المعادلة متعددة الحدود التالية:${\textstyle f_{z}(x)=f(xz)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)}$أين${\displaystyle z}$ هو عنصر من${\displaystyle \mathbb {F} _{p}}$إذا أمكن تمثيل هذه متعددة الحدود كحاصل ضرب${\displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)}$ثم من حيث كثير الحدود الأولي، فهذا يعني أن${\displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)}$، مما يوفر التحليل اللازم لـ${\displaystyle f(x)}$[ ^{1 ] [ 7 ]​}

بسبب معيار أويلر ، لكل حد أحادي${\displaystyle (x-\lambda )}$تتحقق إحدى الخصائص التالية فقط: ^{[ 1 ]}

1. الحدّ الواحد يساوي${\displaystyle x}$لو${\displaystyle \lambda =0}$،
2. يقسم الحد الأحادي${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$لو${\displaystyle \lambda }$ هو الباقي التربيعي modulo${\displaystyle p}$،
3. يقسم الحد الأحادي${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$لو${\displaystyle \lambda }$ هو باقي تربيعي modulo${\displaystyle p}$.

وبالتالي إذا${\displaystyle f_{z}(x)}$لا يقبل القسمة على${\displaystyle x}$والتي يمكن التحقق منها بشكل منفصل، ثم${\displaystyle f_{z}(x)}$يساوي حاصل ضرب القواسم المشتركة الكبرى${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$و${\displaystyle \gcd(f_{z}(x);g_{1}(x))}$[ ^{7 ]​}

تؤدي الخاصية المذكورة أعلاه إلى الخوارزمية التالية: ^{[ 1 ]}

1. احسب معاملات${\displaystyle f_{z}(x)=f(xz)}$،
2. احسب باقي قسمة${\textstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},\ldots ,x^{2^{\lfloor \log _{2}p\rfloor }}}$modulo${\displaystyle f_{z}(x)}$بتربيع كثير الحدود الحالي وأخذ الباقي modulo${\displaystyle f_{z}(x)}$،
3. باستخدام عملية الأسس بالتربيع وكثيرات الحدود المحسوبة في الخطوات السابقة، احسب باقي قسمة${\textstyle x^{(p-1)/2}}$modulo${\textstyle f_{z}(x)}$،
4. لو${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)}}}$ثم${\displaystyle \gcd }$تُقدّم الأمثلة المذكورة أدناه تحليلًا غير تافه لـ${\displaystyle f_{z}(x)}$،
5. وإلا فإن جميع جذور${\displaystyle f_{z}(x)}$إما أن تكون بقايا أو غير بقايا في آن واحد، ويتعين على المرء اختيار الآخر.${\displaystyle z}$.

لو${\displaystyle f(x)}$يقبل القسمة على كثير حدود أولي غير خطي${\displaystyle g(x)}$زيادة${\displaystyle \mathbb {F} _{p}}$ثم عند الحساب${\displaystyle \gcd }$مع${\displaystyle g_{0}(x)}$و${\displaystyle g_{1}(x)}$سيحصل المرء على تحليل غير تافه لـ${\displaystyle f_{z}(x)/g_{z}(x)}$وبالتالي، تسمح هذه الخوارزمية بإيجاد جميع جذور كثيرات الحدود العشوائية على${\displaystyle \mathbb {F} _{p}}$.

ضع في اعتبارك المعادلة${\textstyle x^{2}\equiv a{\pmod {p}}}$يحتوي على عناصر${\displaystyle \beta }$و${\displaystyle -\beta }$كجذورها. حل هذه المعادلة يكافئ تحليل كثير الحدود${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$زيادة${\displaystyle \mathbb {F} _{p}}$في هذه الحالة المحددة، يكفي حساب فقط${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$بالنسبة لهذه المعادلة متعددة الحدود، ستتحقق إحدى الخصائص التالية فقط:

1. القاسم المشترك الأكبر يساوي${\displaystyle 1}$وهذا يعني أن${\displaystyle z+\beta }$و${\displaystyle z-\beta }$كلاهما عبارة عن بواقي غير تربيعية،
2. القاسم المشترك الأكبر يساوي${\displaystyle f_{z}(x)}$وهذا يعني أن كلا العددين عبارة عن بواقي تربيعية،
3. القاسم المشترك الأكبر يساوي${\displaystyle (xt)}$وهذا يعني أن أحد هذه الأرقام بالضبط هو الباقي التربيعي.

في الحالة الثالثة، يكون القاسم المشترك الأكبر مساوياً لأحد القيمتين التاليتين:${\displaystyle (xz-\beta )}$أو${\displaystyle (x-z+\beta )}$يسمح ذلك بكتابة الحل على النحو التالي:${\textstyle \beta =(tz){\pmod {p}}}$[ ^{1 ]​}

لنفترض أننا بحاجة إلى حل المعادلة${\textstyle x^{2}\equiv 5{\pmod {11}}}$لذلك نحتاج إلى تحليل المقدار إلى عوامله الأولية.${\displaystyle f(x)=x^{2}-5=(x-\beta )(x+\beta )}$ضع في اعتبارك بعض القيم المحتملة لـ${\displaystyle z}$:

1. يترك${\displaystyle z=3}$. ثم${\displaystyle f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4}$، هكذا${\displaystyle \gcd(x^{2}-6x+4;x^{5}-1)=1}$كلا الرقمين${\displaystyle 3\pm \beta }$هي بواقي غير تربيعية، لذلك نحتاج إلى أخذ شيء آخر${\displaystyle z}$.

1. يترك${\displaystyle z=2}$. ثم${\displaystyle f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1}$، هكذا${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$ويترتب على ذلك${\textstyle x-9=x-2-\beta }$، لذا${\displaystyle \beta \equiv 7{\pmod {11}}}$و${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$.

أظهر فحص يدوي أن ذلك بالفعل${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11}}}$و${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11}}}$.