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

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

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

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

خصائص

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

انظر أيضا

• عدد كارميكائيل.

مراجع

1. Carl Pomerance؛ John L. Selfridge؛ Samuel S. Wagstaff, Jr. (يوليو 1980). "The pseudoprimes to 25·10^9" (PDF). Mathematics of Computation. ج. 35 ع. 151: 1003–1026. DOI:10.1090/S0025-5718-1980-0572872-7. JSTOR:2006210. مؤرشف من الأصل (PDF) في 2016-12-20.

وصلات خارجية

• The prime glossary – Probable prime
• The PRP Top 10000 (the largest known probable primes)
• Generalized repunit probable primes