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

'''اختبار أ.ك.أس لأولية عدد ما''' {{إنج|AKS primality test}} <ref>{{استشهاد ويب| مسار = https://rosettacode.org/wiki/AKS_test_for_primes | عنوان = معلومات عن اختبار أ.ك.أس لأولية عدد ما على موقع rosettacode.org | ناشر = rosettacode.org| مسار أرشيف = https://web.archive.org/web/20200915114735/http://rosettacode.org/wiki/AKS_test_for_primes | تاريخ أرشيف = 15 سبتمبر 2020 }}</ref><ref>{{استشهاد ويب| مسار = http://mathworld.wolfram.com/AKSPrimalityTest.html | عنوان = معلومات عن اختبار أ.ك.أس لأولية عدد ما على موقع mathworld.wolfram.com | ناشر = mathworld.wolfram.com| مسار أرشيف = https://web.archive.org/web/20200318163112/https://mathworld.wolfram.com/AKSPrimalityTest.html | تاريخ أرشيف = 18 مارس 2020 }}</ref> هي [[خوارزمية حتمية|خوارزمية قطعية]] تحدد ما إذا كان عدد طبيعي ما [[عدد أولي|أوليا]] أم لا.
وضع هذه الخواراميةَ [[مانيندرا أغراوال]] وتلميذاه [[نيراج كايال]] و[[نيتين ساكسينا]]. كان ذلك في السادس من غشت/أغسطس سنة 2002. هم علماء حاسوب يعملون في [[المؤسسة الهندية للتكنولوجيا في كانبور]]. عنوان المقال الذي احتوى على هذا الاختراع هو '''''''الأولية في بي'''''''<ref name="AKS">{{استشهاد بدورية محكمة |مؤلف1-الأول=Manindra |مؤلف1-الأخير=Agrawal |مؤلف2-الأول=Neeraj |مؤلف2-الأخير=Kayal |مؤلف3-الأول=Nitin |مؤلف3-الأخير=Saxena |مسار=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |عنوان=PRIMES is in P |صحيفة=[[حوليات الرياضيات]] |المجلد=160 |سنة=2004 |العدد=2 |صفحات=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |doi-access=free | مسار أرشيف = https://web.archive.org/web/20220510144039/https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf | تاريخ أرشيف = 10 مايو 2022 }}</ref>
عرفت بعد ذلك بعض التحسينات خاصة سنة 2003. هذه الخوارزمية هي الأولى من نوعها التي تحدد ما إذا كان عدد طبيعي ما أوليا أو مؤلفا، في [[تعقيد الوقت|وقت يحسب بمتعددة للحدود]]، بدون الاعتماد على أي [[حدسية (رياضيات)|حدسية رياضياتية]]، [[فرضية ريمان المعممة]] مثالا.
في عام 2006، حصل الباحثون الثلاثة على كل من [[جائزة جودل]] و[[جائزة فولكرسن]].

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

== وصف الخوارزمية ==
ترتكز فكرة الخوارزمية على المتساوية الصالحة لكل [[عدد أولي]]، والتي هي تعميم [[مبرهنة فيرما (توضيح)|لمبرهنة فيرما]].

ليكن a [[عدد صحيح|عددا صحيحا]] و n [[عدد طبيعي|عددا طبيعيا]] أكبر من 1 قطعا، حيث a و n [[أولية نسبيا|أوليان فيما بينهما]]. العدد n أولي [[إذا وفقط إذا]] كان <math>(x+a)^N\equiv x^N+a \mod N</math>.

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

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

== مراحل الخوارزمية ==
ليكن n عددا طبيعيا أكبر من 2.
# إذا وُجد عددان <math>a, b\in\mathbb{N}</math> حيث <math>a>1 \,</math> و<math>b>1 \,</math>، وحيث <math>n=a^b \,</math>، أي أن n [[قوة كاملة]]، فإن العدد n [[عدد مؤلف|مركب]].
# حدد أصغر [[عدد صحيح]] طبيعي r حيث [[رتبة جدائية|رتبة]] n في <math>\mathbb{Z}_{/r\mathbb{Z}} \,</math> تكون أكبر من <math>4 \log (n)^2 \,</math>.
# إذا كان <math>1 <a \wedge n <n </math> لعدد صحيح <math>a \le r</math>، فالعدد مركب.
# إذا كان ''n'' ≤ ''r'', فإن العدد n أولي.
# For {{تعبير رياضي|size=100%|1=''a''&nbsp;=&nbsp;1}} to <math>\left\lfloor \sqrt{\varphi(r)}\log_2(n) \right\rfloor</math> افعل ما يلي
#: if (''X''+''a'')<sup>''n''</sup>≠ ''X''<sup>''n''</sup>+''a'' (mod ''X''<sup>''r''</sup> − 1,''n''), العدد n مركب'';
# العدد n أولي.

== مراجع ==
{{مراجع}}
{{شريط بوابات|الهند|تعمية|رياضيات|علم الحاسوب}}

{{خوارزميات نظرية الأعداد}}

[[تصنيف:اختبارات أولية العدد]]
[[تصنيف:حقول منتهية]]