مرجع
آخر الزيارات

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

467 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: اختبار أ.ك.أس لأولية عدد ما هي خوارزمية قطعية تحدد ما إذا كان عدد طبيعي ما أوليا أم لا. في هذه المقالة 4 أقسام: «For to افعل ما يلي»، «مراحل الخوارزمية» و«وصف الخوارزمية» وغيرها.
المحتويات
  1. For to افعل ما يلي
  2. مراحل الخوارزمية
  3. وصف الخوارزمية
  4. أهمية الخوارزمية

بدايةً، اختبار أ.ك.أس لأولية عدد ما هي خوارزمية قطعية تحدد ما إذا كان عدد طبيعي ما أوليا أم لا. وتعرض الأقسام التالية جوانب أخرى من الموضوع.

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

وفي هذا السياق، في عام 2006، حصل الباحثون الثلاثة على كل من جائزة جودل وجائزة فولكرسن.

كذلك، وضع هذه الخواراميةَ مانيندرا أغراوال وتلميذاه نيراج كايال ونيتين ساكسينا. كان ذلك في السادس من غشت/أغسطس سنة 2002. هم علماء حاسوب يعملون في المؤسسة الهندية للتكنولوجيا في كانبور. عنوان المقال الذي احتوى على هذا الاختراع هو الأولية في بي

For to افعل ما يلي

العدد n أولي.

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

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

  • ليكن n عددا طبيعيا أكبر من 2.
  • إذا وُجد عددان حيث و، وحيث ، أي أن n قوة كاملة، فإن العدد n مركب.
  • حدد أصغر عدد صحيح طبيعي r حيث رتبة n في تكون أكبر من .
  • إذا كان لعدد صحيح ، فالعدد مركب.
  • إذا كان n ≤ r, فإن العدد n أولي.

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

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

يأخد وقتا حيث يجب دراسة n معامل في الحالة الأسوء.

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

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

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

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

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

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

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.