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

اختبار أولية عدد ما (بالإنجليزية: Primality test)‏ هو خوارزمية هدفها تحديدُ إن كان عدد طبيعي ما أوليا أم لا. تستعمل هذه الخوارزميات في مجال التعمية وفي مجالات أخرى من الرياضيات. تختلف عن خوارزميات تحليل عدد صحيح إلى عوامل في كونها أنها لا تعطي قواسم العدد الذي نحن بصدد اختبار أوليته. خوارزميات تحليل عدد صحيح إلى عوامل، كما يدل على ذلك اسمها، تعطي قواسم هذا العدد. من حيث التعقد الحسابي، يعتقد أن تعميل عدد طبيعي هو معضلة صعبة، بينما اختبار أولية عدد، هو مقارنةً، معضلة سهلة حيث تعقد الوقت لخوارزميات اختبار أولية عدد هو بدلالة متعددة للحدود مدخلها طول العدد الذي يراد اختبار أوليته. بعض الاختبارات تبرهن على أن عدد ما هو أولى، بينما تبرهن بعضها أن عددا ما هو مؤلف. اختبار ميلر-رابن لأولية عدد ما مثال على ذلك.

الطرق الساذجة

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

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

(p-1)!\equiv -1{\pmod {p}}\,

الاختبارات الاحتمالية

تمكن هذه الاختبارات من القول أن عددا طبيعيا ما عددٌ أولي محتمل.

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

أبسط اختبار احتمالي لأولية عدد ما هو اختبار فيرما (حاليا بل هو اختبار تألف عدد طبيعي بدلا من أوليته). يعمل كما يلي:

ليكن n عددا طبيعيا معلوما. اختر عددا طبيعيا a أوليا نسبيا مع العدد n، ثم احسب aⁿ^{− 1} بتردد n. إذا كانت النتيجة مختلفة عن الواحد، فأن العدد n مؤلف. قد يكون أوليا غير ذلك.