عدد أولي محتمل

في نظرية الأعداد، عدد أولي محتمل (بالإنجليزية :(PRP) Probable prime) هو عدد طبيعي يستوفي شرطا ما تحققه جميع الأعداد الأولية. ولكن لا تستوفيه معظم الأعداد المؤلفة. تختلف هذه شروط حسب نوع العدد الأولي المحتمل . في حين أنه قد يكون هناك عدد أولي محتمل ولكنه مؤلف (يسمى عدد شبه أولي Pseudoprimes) ، يتم اختيارالشرط بشكل عام من أجل جعل مثل هذه الاستثناءات نادرة.

اختبار فيرما لأولية عدد ما ، والذي يعتمد على نظرية فيرما الصغرى ، يعمل على النحو التالي : ليكن  عدد صحيح ، اختر عددًا صحيحًا  لا يكون مضاعفًا لـ  ؛ (عادةً ، نختار  في النطاق ). احسب   إذا لم تكن النتيجة 1 ، فإن  تكون مركبة. إذا كانت النتيجة 1 ، فمن المحتمل أن يكون  عددًا أوليًا ؛ بحيث يسمى  عددًا أوليًا محتملاً للأساس .

بالنسبة لأساس  ثابت ، من غير المألوف أن يكون عدد مؤلف عددُُ أولي محتملاً (أي عدد شبه أولي) لذلك الأساس. على سبيل المثال ، حتى  ، يوجد عددا مؤلفا فرديًا ، ولكن يوجد فقط  عددا شبه أولي للأساس 2. عدد الأعداد الأولية الفردية في نفس المجال هو .

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

انظر أيضا 
 عدد كارميكائيل.

مراجع

وصلات خارجية 
 The prime glossary – Probable prime
 The PRP Top 10000 (the largest known probable primes)
 Generalized repunit probable primes

الأعداد شبه الأولية