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

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