عدد أولي محتمل
تعريفًا بالموضوع، في نظرية الأعداد، عدد أولي محتمل (بالإنجليزية :(PRP) Probable prime) هو عدد طبيعي يستوفي شرطا ما تحققه جميع الأعداد الأولية. ولكن لا تستوفيه أغلب الأعداد المؤلفة. تختلف هذه شروط حسب نوع العدد الأولي المحتمل . في حين أنه قد يكون هناك عدد أولي محتمل ولكنه مؤلف (يسمى عدد شبه أولي Pseudoprimes) ، يتم اختيارالشرط بشكل عام من أجل جعل مثل هذه الاستثناءات نادرة. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
من جانب آخر، اختبار فيرما لأولية عدد ما ، والذي يعتمد على نظرية فيرما الصغرى ، يعمل على النحو التالي : ليكن عدد صحيح ، اختر عددًا صحيحًا لا يكون مضاعفًا لـ ؛ (عادةً ، نختار في النطاق ). احسب إذا لم تكن النتيجة 1 ، فإن تكون مركبة. إذا كانت النتيجة 1 ، فمن المحتمل أن يكون عددًا أوليًا ؛ بحيث يسمى عددًا أوليًا محتملاً للأساس .
إضافةً إلى ذلك، بالنسبة لأساس ثابت ، من غير المألوف أن يكون عدد مؤلف عددُُ أولي محتملاً (أي عدد شبه أولي) لذلك الأساس. مثلًا ، حتى ، يوجد عددا مؤلفا فرديًا ، ولكن يوجد فقط عددا شبه أولي للأساس 2. عدد الأعداد الأولية الفردية في نفس المجال هو .
خصائص
كذلك، الأولية المحتملة هي أساس لخوارزميات اختبار الأولية الفعالة ، والتي تجد تطبيقات كثيرة في التشفير. عادة ما تكون هذه الخوارزميات احتمالية بطبيعتها. الفكرة هي أنه على الرغم من وجود أعداد أولية محتملة مؤلفة لأساس لأي ثابت ، فقد نأمل أنه يوجد ثابت بالنسبة لأي عدد مؤلف ، بحيث إذا اخترنا عشوائيًا ، فإن احتمال أن هو شبه أولي للأساس هو على أقصى تقدير .
The prime glossary – Probable prime
The PRP Top 10000 (the largest known probable primes)
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟