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

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

اختبار فيرما لأولية عدد ما ، والذي يعتمد على نظرية فيرما الصغرى ، يعمل على النحو التالي : ليكن $n$ عدد صحيح ، اختر عددًا صحيحًا $a$ لا يكون مضاعفًا لـ $n$ ؛ (عادةً ، نختار $a$ في النطاق $1<a<n-1$ ). احسب $a^{n-1}{\pmod {n}}$ إذا لم تكن النتيجة 1 ، فإن $n$ تكون مركبة. إذا كانت النتيجة 1 ، فمن المحتمل أن يكون $n$ عددًا أوليًا ؛ بحيث يسمى $n$ عددًا أوليًا محتملاً للأساس $a$ .^[1]

بالنسبة لأساس $a$ ثابت ، من غير المألوف أن يكون عدد مؤلف عددُُ أولي محتملاً (أي عدد شبه أولي) لذلك الأساس. على سبيل المثال ، حتى $25\times 10^{9}$ ، يوجد $11,408,012,595$ عددا مؤلفا فرديًا ، ولكن يوجد فقط $21853$ عددا شبه أولي للأساس 2. عدد الأعداد الأولية الفردية في نفس المجال هو $1,091,987,404$ .

خصائص

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