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

أحد الأعداد الطبيعية

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

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

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

خصائص

عدل

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

انظر أيضا

عدل

مراجع

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

وصلات خارجية

عدل