خوارزمية AKS

خوارزمية AKS نسبة لواضعيها Agrawal وتلميذيه Kayal وSaxena. هي أول خوارزمية تحدد ما إذا كان عدد ما أولي أم لا. وقد ظهرت سنة 2002 لأول مرة وعهدت بعد ذلك بعض التحسينات خاصة سنة 2003.

أهمية الخوارزمية

قبل اكتشاف الخوارزمية، كانت هناك عدة خوارزميات تميز العدد المركب من العدد الأولي، لكن معظمها كان إما احتماليا أويعتمد على حدسيات لم تثبت صحتها بعد كفرضية ريمان. لكن خوارزمية AKS لا تعتمد على أي حدسية وليست احتمالية.

وصف الخوارزمية

ترتكز فكرة الخوارزمية على المتساوية الصالحة لكل عدد أولي، والتي هي تعميم لمبرهنة فيرما.

ليكن a عدد نسبي وn عدد طبيعي أكبر من 1 بترا، حيث a وn أوليان فيما بينهما. العدد n أولي إذا وفقط إذا كان ${\displaystyle (x+a)^{N \equiv x^{N +a\mod N$ .

تتيح هذه المتساوية معيارا بسيطا لاختبار الإوالية : ليكن n عدد، يكفي اختيار a أولي مع n ثم التحقق من حتى الصيغة سليمة. إلا حتى هذا يأخد وقتا ${\displaystyle O(n)\,$ حيث يجب دراسة n معامل في الحالة الأسوء.

لتقليص العدد، يكفي التحقق من صحة المتساوية داخل الحلقة ${\displaystyle {\frac {\mathbb {Z _{/n\mathbb {Z \left[X\right] {(X^{r -1)\mathbb {Z _{/n\mathbb {Z \left[X\right]$ .

مراحل الخوارزمية

ليكن n عدد طبيعي أكبر من 2.

إذا كان ${\displaystyle n=a^{b \,$
تحديد أصغر عدد سليم طبيعي r بحيث رتبة n في ${\displaystyle \mathbb {Z _{/r\mathbb {Z \,$ أكبر من ${\displaystyle 4\log(n)^{2 \,$ .
إذا كان ${\displaystyle 1<a\wedge n<n$ لعدد سليم ${\displaystyle a\leq r$ ، فالعدد مركب.