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

في نظرية الأعداد، عدد أولي محتمل (بالإنجليزية :(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.

وصلات خارجية

  • أيقونة بوابةبوابة نظرية الأعداد
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.