يفتقر محتوى هذه المقالة إلى مصادر موثوقة

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
Question book-new.svg
تعرَّف على طريقة التعامل مع هذه المسألة من أجل إزالة هذا القالب.يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوقة. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016)

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

أهمية الخوارزمية[عدل]

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

وصف الخوارزمية[عدل]

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

ليكن a عددا نسبيا و n عددا طبيعيا أكبر من 1 قطعا، حيث a و n أوليان فيما بينهما. العدد n أولي إذا وفقط إذا كان .

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

لتقليص العدد، يكفي التحقق من صحة المتساوية داخل الحلقة .

مراحل الخوارزمية[عدل]

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

  1. إذا كان لكل و فالعدد مركب.
  2. تحديد أصغر عدد صحيح طبيعي r بحيث رتبة n في أكبر من .
  3. إذا كان لعدد صحيح ، فالعدد مركب.
Nuvola apps edu mathematics-ar.svg
هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. شارك في تحريرها.