عرض مصدر اختبار أولية عدد ما

{{لا مصدر|تاريخ=يناير 2022}}
[[ملف:Mersene39.png|تصغير|200بك|يسار]]
'''اختبار أولية عدد ما''' {{إنج|Primality test}} هو [[خوارزمية]] هدفها تحديدُ إن كان عدد طبيعي ما [[عدد أولي|أوليا]] أم لا. تستعمل هذه الخوارزميات في مجال [[تعمية (توضيح)|التعمية]] وفي مجالات أخرى من الرياضيات. تختلف عن خوارزميات [[تحليل عدد صحيح إلى عوامل]] في كونها أنها لا تعطي قواسم العدد الذي نحن بصدد اختبار أوليته. خوارزميات [[تحليل عدد صحيح إلى عوامل]]، كما يدل على ذلك اسمها، تعطي قواسم هذا العدد. من حيث التعقد الحسابي، يعتقد أن تعميل عدد طبيعي هو معضلة صعبة، بينما اختبار أولية عدد، هو مقارنةً، معضلة سهلة حيث [[تعقيد الوقت|تعقد الوقت]] لخوارزميات اختبار أولية عدد هو بدلالة متعددة للحدود مدخلها طول العدد الذي يراد اختبار أوليته. بعض الاختبارات تبرهن على أن عدد ما هو أولى، بينما تبرهن بعضها أن عددا ما هو مؤلف. [[اختبار ميلر ورابين لأولية عدد ما|اختبار ميلر-رابن لأولية عدد ما]] مثال على ذلك.

== الطرق الساذجة ==
أبسط اختبار لأولية [[عدد طبيعي]] ما هو [[قسمة متكررة|القسمة المتكررة]]: ليكن n عددا طبيعيا ما. تتمثل هذه الطريقة في النظر إلى [[قاسم (رياضيات)|قابلية قسمة]] هذا العدد على [[عدد أولي]] ما محصور بين الاثنين والجذر التربيعي للعدد n (أي أن القسمة لا تترك [[باق (رياضيات)|باقيا]]). إذا وُجد هذا القاسم، فإنه يقال عن العدد n أنه [[عدد مؤلف]] (أو مركب)، وإذا لم يوجد، فإنه يقال عن العدد n أنه أولي.

انظر إلى [[غربال إراتوستينس]] وإلى [[مبرهنة ويلسون]].

:<math>(p-1)! \equiv -1\pmod p \,</math>

== الاختبارات الاحتمالية ==
تمكن هذه الاختبارات من القول أن عددا طبيعيا ما [[عدد أولي محتمل|عددٌ أولي محتمل]].
=== اختبار فيرما لأولية عدد ما ===
أبسط اختبار احتمالي لأولية عدد ما هو [[اختبار فيرما لأولية عدد ما|اختبار فيرما]] (حاليا بل هو اختبار تألف عدد طبيعي بدلا من أوليته). يعمل كما يلي:
:ليكن n عددا طبيعيا معلوما. اختر عددا طبيعيا a [[أولية نسبيا|أوليا نسبيا]] مع العدد n، ثم احسب ''a<sup>n</sup>''<sup> − 1</sup> [[حسابيات معيارية|بتردد]] ''n''. إذا كانت النتيجة مختلفة عن الواحد، فأن العدد n مؤلف. قد يكون أوليا غير ذلك.

=== اختبارا ميلير-رابن وصولوفاي-شتراسن لأولية عدد ما ===
انظر إلى [[اختبار ميلر ورابين لأولية عدد ما|اختبار ميلر-رابن لأولية عدد ما]] وإلى [[رمز جاكوبي]].

=== اختبار فروبنيوس لأولية عدد ما ===
انظر إلى [[عدد لوكاس شبه الأولي]].

=== اختبارات أخرى ===

== الاختبارات القطعية السريعة ==
انظر إلى [[اختبار أولية عدد ما لبوكلينغتن]] وإلى [[فرضية ريمان المعممة]] وإلى [[مانيندرا أغراوال]] وإلى [[عدد صوفي جيرمين الأولي]] وإلى [[اختبار أ.ك.أس لأولية عدد ما]].

== التعقد ==
في [[نظرية التعقيد الحسابي]]، من السهل البرهان على أن عملية اختبار أولية عددا ما هي [[كو-إن بي]].

== الطرق المعتمدة على نظرية الأعداد ==
انظر إلى [[اختبار لوكاس لأولية عدد ما]] وإلى [[مبرهنة بروث]] وإلى [[رتبة جدائية|مضاعف مرتب]].

== مراجع ==
{{مراجع}}

== وصلات خارجية ==
{{خوارزميات نظرية الأعداد}}
{{شريط بوابات|تعمية|رياضيات|علم الحاسوب}}

{{بذرة رياضيات}}

[[تصنيف:خوارزميات تعمية بالمفتاح العام]]
[[تصنيف:اختبارات أولية العدد]]