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

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

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

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

خصائص

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

انظر أيضا

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

مراجع

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

وصلات خارجية

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.

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

[1]

ع ن ت أصناف الأعداد الأولية
من حيث الصيغة	فيرما ( $2 2 n + 1$ ) ميرسين ( $2 p - 1$ ) عدد ميرسين المزدوج ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) عدد أولي عاملي Primorial ( $p n # \pm 1$ ) أقليدس( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Carol $(2 n - 1) 2 - 2$ Kynea $(2 n + 1) 2 - 2$ Leyland ( $x y + y x$ ) ثابت( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $خطأ في التعبير: علامة ترقيم لم نتعرف عليها «'».$ )
By integer sequence	فيبوناتشي لوكاس بيل Newman–Shanks–Williams بيرن تجزئة (نظرية الأعداد) عدد بيل رقم موتسكين
من حيث الخصائص	Wieferich (pair) Wall–Sun–Sun Wolstenholme عدد ويلسون الأولي محظوظ Fortunate عدد رامانجن الأولي Pillai عدد أولي نظامي Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient
أساس (رياضيات)-dependent	عدد سعيد Dihedral Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable دائرية Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin Tetradic
من حيث الشكل	عددان أوليان توأم ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k−Tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) عدد تشين الأولي Sophie Germain ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Safe ( $p, (p - 1)/2$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
من حيث عدد الأرقام	Titanic (1,000+ digits) Gigantic (10,000+ digits) Mega (1,000,000+ digits) أكبر عدد أولي معروف
عدد مركب	عدد أيزنشتاين الأولي عدد صحيح غاوسي
عدد غير أولي	عدد شبه أولي كاتالان Elliptic أويلر أويلر–جاكوبي أعداد فيرما شبه الأولية فروبنيوس لوكاس سومر–لوكاس Strong عدد كارميكائيل Almost prime عدد نصف أولي Interprime Pernicious
Related topics	عدد أولي محتمل Industrial-grade prime عدد غير شرعي صيغة للأعداد الأولية فجوة أولية
الأعداد الأولية الستون الأولى	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
قائمة الأعداد الأولية