خوارزمية AKS

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

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

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

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

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

ليكن a عدد نسبي و n عدد طبيعي أكبر من 1 قطعا، حيث a و n أوليان فيما بينهما. العدد n أولي إذا و فقط إذا كان خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x+a)^N\equiv x^N+a \mod N} .

تتيح هذه المتساوية معيارا بسيطا لاختبار الإوالية : ليكن n عدد، يكفي اختيار a أولي مع n ثم التحقق من أن الصيغة صحيحة. إلا أن هذا يأخد وقتا خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n) \,} حيث يجب دراسة n معامل في الحالة الأسوء.

لتقليص العدد، يكفي التحقق من صحة المتساوية داخل الحلقة خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathbb{Z}_{/n\mathbb{Z}\left[ X \right]}}{(X^r-1) \mathbb{Z}_{/n\mathbb{Z}\left[ X \right]}}} .

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

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

1. إذا كان $n=a^{b}\,$ لكل $a\in \mathbb {N}$ و خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle b>1 \,} فالعدد مركب.
2. تحديد أصغر عدد صحيح طبيعي r بحيث رتبة n في خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_{/r\mathbb{Z}} \,} أكبر من خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4 \log (n)^2 \,} .
3. إذا كان خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 < a \wedge n < n } لعدد صحيح خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \le r} ، فالعدد مركب.