إتقان موضوع عدد أولي محتمل

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

اختبار فيرما لأولية عدد ما ، والذي يعتمد على نظرية فيرما الصغرى ، يعمل على النحو التالي : ليكن







n





{\displaystyle n}



عدد صحيح ، اختر عددًا صحيحًا







a





{\displaystyle a}



لا يكون مضاعفًا لـ







n





{\displaystyle n}



؛ (عادةً ، نختار







a





{\displaystyle a}



في النطاق







1

<

a

<

n

−

1





{\displaystyle 1


). احسب









a



n

−

1









(

mod



n

)







{\displaystyle a^{n-1}{\pmod {n}}}



إذا لم تكن النتيجة 1 ، فإن







n





{\displaystyle n}



تكون مركبة. إذا كانت النتيجة 1 ، فمن المحتمل أن يكون







n





{\displaystyle n}



عددًا أوليًا ؛ بحيث يسمى







n





{\displaystyle n}



عددًا أوليًا محتملاً للأساس







a





{\displaystyle a}



.

بالنسبة لأساس







a





{\displaystyle a}



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







25

×



10



9









{\displaystyle 25\times 10^{9}}



، يوجد







11

,

408

,

012

,

595





{\displaystyle 11,408,012,595}



عددا مؤلفا فرديًا ، ولكن يوجد فقط







21853





{\displaystyle 21853}



عددا شبه أولي للأساس 2. عدد الأعداد الأولية الفردية في نفس المجال هو







1

,

091

,

987

,

404





{\displaystyle 1,091,987,404}



.