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

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

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

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

ليكن 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.

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

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

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

• بوابة الهند
• بوابة رياضيات
• بوابة تعمية