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

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

372 كلمة•0 مشاهدة•🗒️ منذ 7 أيام
باختصار: اختبار أولية عدد ما هو خوارزمية هدفها تحديدُ إن كان عدد طبيعي ما أوليا أم لا. تتناول المقالة 8 أقسام، منها «الطرق الساذجة»، «الاختبارات الاحتمالية» و«التعقد».
المحتويات
  1. الطرق الساذجة
  2. الاختبارات الاحتمالية
  3. التعقد
  4. اختبارا ميلير-رابن وصولوفاي-شتراسن لأولية عدد ما
  5. الاختبارات القطعية السريعة
  6. اختبار فروبنيوس لأولية عدد ما
  7. اختبار فيرما لأولية عدد ما
  8. الطرق المعتمدة على نظرية الأعداد
اختبار أولية عدد ما

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

الطرق الساذجة

وفي هذا الصدد، أبسط اختبار لأولية عدد طبيعي ما هو القسمة المتكررة: ليكن n عددا طبيعيا ما. تتمثل هذه الطريقة في النظر إلى قابلية قسمة هذا العدد على عدد أولي ما محصور بين الاثنين والجذر التربيعي للعدد n (أي أن القسمة لا تترك باقيا). إذا وُجد هذا القاسم، فإنه يقال عن العدد n أنه عدد مؤلف (أو مركب)، وإذا لم يوجد، فإنه يقال عن العدد n أنه أولي.

انظر إلى غربال إراتوستينس وإلى مبرهنة ويلسون.

الاختبارات الاحتمالية

وفي السياق ذاته، تمكن هذه الاختبارات من القول أن عددا طبيعيا ما عددٌ أولي محتمل.

التعقد

من جانب آخر، في نظرية التعقيد الحسابي، من السهل البرهان على أن عملية اختبار أولية عددا ما هي كو-إن بي.

اختبارا ميلير-رابن وصولوفاي-شتراسن لأولية عدد ما

انظر إلى اختبار ميلر-رابن لأولية عدد ما وإلى رمز جاكوبي.

الاختبارات القطعية السريعة

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

اختبار فروبنيوس لأولية عدد ما

انظر إلى عدد لوكاس شبه الأولي.

اختبارات أخرى

اختبار فيرما لأولية عدد ما

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

وفي هذا السياق، أبسط اختبار احتمالي لأولية عدد ما هو اختبار فيرما (في الوقت الحالي بل هو اختبار تألف عدد طبيعي بدلا من أوليته). يعمل كما يلي:

الطرق المعتمدة على نظرية الأعداد

مراجع

في هذا الإطار، انظر إلى اختبار لوكاس لأولية عدد ما وإلى مبرهنة بروث وإلى مضاعف مرتب.

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

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

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