اختبار أ.ك.أس لأولية عدد ما

اختبار أ.ك.أس لأولية عدد ما (بالإنجليزية: AKS primality test)‏ هي خوارزمية قطعية تحدد ما إذا كان عدد طبيعي ما أوليا أم لا. وضع هذه الخواراميةَ مانيندرا أغراوال وتلميذاه نيراج كايال ونيتين ساكسينا. كان ذلك في السادس من غشت/أغسطس سنة 2002. هم علماء حاسوب يعملون في المؤسسة الهندية للتكنولوجيا في كانبور. عنوان المقال الذي احتوى على هذا الاختراع هو ''الأولية في بي'' عرفت بعد ذلك بعض التحسينات خاصة سنة 2003. هذه الخوارزمية هي الأولى من نوعها التي تحدد ما إذا كان عدد طبيعي ما أوليا أو مؤلفا، في وقت يحسب بمتعددة للحدود، بدون الاعتماد على أي حدسية رياضياتية، فرضية ريمان المعممة مثالا. في عام 2006، حصل الباحثون الثلاثة على كل من جائزة جودل وجائزة فولكرسن.

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

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

• خوارزمية أ. ك. إس يمكن أن تستعمل لاختبار أولية عدد طبيعي ما مهما كان شكله. هناك العديد من الخوارزميات التي تحقق هذا الهدف، ولكن عند أعداد طبيعية خاصة. على سبيل المثال، اختبار لوكاس-ليهمر يعمل فقط على عدد ميرسين الأولي بينما يعمل اختبار بيبين فقط على عدد فيرما.
• خوارزمية أ. ك. إس قطعية. إنها تجيب بشكل قطعي لا شك فيه ولا احتمال فيه على السؤال التالي: هل العدد المعين أولى أم لا ؟. اختبار ميلر-رابن لأولية عدد ما، على سبيل المثال، هو خوارزمية تستغرق من الوقت ما يحسب بمتعددة للحدود، تماما كخوارزمية خوارزمية أ. ك. إس ، ولكنها ليست قطعية وإنما هي احتمالية.
• اختبار أ. ك. إس هو خوارزمية صحيحة ولا تفترض صحة أي فرضية أو حدسية. على سبيل المقارنة، صيغة ميلر من اختبار ميلر-رابن لأولية عدد ما هي قطعية وتستغرق من الوقت ما يحسب بمتعددة للحدود، ولكن صحتها تعتمد على صحة فرضية ريمان المعممة، والتي لم يبرهن عليها بعد، كما يدل على ذلك اسمها.

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

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

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

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

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

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

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

1. إذا وُجد عددان $a,b\in \mathbb{N}$ حيث $a>1$ و$b>1$، وحيث $n=a^b$، أي أن n قوة كاملة، فإن العدد n مركب.
2. حدد أصغر عدد صحيح طبيعي r حيث رتبة n في ${\mathbb{Z}}_{/r\mathbb{Z}}$ تكون أكبر من $4\log (n{)}^2$.
3. إذا كان $1<a\wedge n<n$ لعدد صحيح $a\le r$، فالعدد مركب.
4. إذا كان n ≤ r, فإن العدد n أولي.
5. For a = 1 to $\lfloor \sqrt{\phi (r)}{\log }_2(n)\rfloor$ افعل ما يلي

   if (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), العدد n مركب;

6. العدد n أولي.