اختبار البدائية

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

اختبار الأعداد الأولية الأبسط هو القسمة التجريبية : إذا كان هناك رقم مدخل، ، تحقق مما إذا كان قابلاً للقسمة على أي عدد أولي بين 2 و (أي ما إذا كانت القسمة لا تترك أي باقٍ ). إذا كان الأمر كذلك، فإن يكون مركبًا . وإلا فهو أولي. ^[1] بالنسبة لأي قاسم ، يجب أن يكون هناك قاسم آخر ، وقاسم أولي لـ ، وبالتالي فإن البحث عن قواسم أولية على الأكثر كافٍ. ${\displaystyle n}$${\displaystyle {\sqrt {n}}}$${\displaystyle n}$${\displaystyle p\geq {\sqrt {n}}}$${\displaystyle n/p\leq {\sqrt {n}}}$${\displaystyle q}$${\displaystyle n/p}$${\displaystyle {\sqrt {n}}}$

على سبيل المثال، فكر في الرقم 100، الذي تكون قواسمه هذه الأرقام:

1، 2، 4، 5، 10، 20، 25، 50، 100.

عند اختبار جميع المقسومات الممكنة حتى ، سيتم اكتشاف بعض المقسومات مرتين . لملاحظة ذلك، ضع في اعتبارك قائمة أزواج المقسومات المكونة من 100: ${\displaystyle n}$

${\displaystyle 1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1}$.

إن المنتجات السابقة هي عكس المنتجات التي ظهرت في وقت سابق. على سبيل المثال، و هما عكس بعضهما البعض. علاوة على ذلك، فإن المقسومين، و . هذه الملاحظة تعمم على الكل : تحتوي جميع أزواج المقسومات على مقسوم أقل من أو يساوي ، لذا فإن الخوارزمية تحتاج فقط إلى البحث عن مقسومات أقل من أو تساوي لضمان اكتشاف جميع أزواج المقسومات. ^[1]${\displaystyle 10\times 10}$${\displaystyle 5\times 20}$${\displaystyle 20\times 5}$${\displaystyle 5\leq {\sqrt {100}}=10}$${\displaystyle 20\geq {\sqrt {100}}=10}$${\displaystyle n}$${\displaystyle n}$${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$

أيضًا، 2 هو عدد أولي يقسم 100، مما يثبت على الفور أن 100 ليس عددًا أوليًا. كل عدد صحيح موجب باستثناء 1 قابل للقسمة على عدد أولي واحد على الأقل وفقًا للنظرية الأساسية في الحساب . لذلك، تحتاج الخوارزمية فقط إلى البحث عن قواسم أولية أقل من أو تساوي . ${\displaystyle {\sqrt {n}}}$

ولمثال آخر، ضع في اعتبارك كيف تحدد هذه الخوارزمية أولية العدد 17. لدينا , والأعداد الأولية الوحيدة هي 2 و3. ولا يقسم أي منهما 17، مما يثبت أن 17 عدد أولي. ولمثال أخير، ضع في اعتبارك 221. لدينا , والأعداد الأولية هي 2 و3 و5 و7 و11 و13. وعند التحقق من كل منها، نكتشف أن , مما يثبت أن 221 ليس عددًا أوليًا. ${\displaystyle 4<{\sqrt {17}}<5}$${\displaystyle \leq {\sqrt {17}}}$${\displaystyle 14<{\sqrt {221}}15}$${\displaystyle \leq {\sqrt {221}}}$${\displaystyle 221/13=17}$

في الحالات التي لا يكون من الممكن فيها حساب قائمة الأعداد الأولية ، من الممكن أيضًا التحقق ببساطة (وببطء) من جميع الأرقام بين و بحثًا عن القواسم. هناك تحسين بسيط إلى حد ما يتمثل في اختبار قابلية القسمة على 2 وعلى الأعداد الفردية فقط بين 3 و ، لأن قابلية القسمة على عدد زوجي تعني قابلية القسمة على 2. ${\displaystyle \leq {\sqrt {n}}}$${\displaystyle 2}$${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$

يمكن تحسين هذه الطريقة بشكل أكبر. لاحظ أن جميع الأعداد الأولية الأكبر من 3 تكون على هيئة عدد صحيح غير سالب و . في الواقع، كل عدد صحيح يكون على هيئة عدد صحيح موجب و . بما أن 2 يقسم و و و 3 يقسم و ، فإن الباقي الوحيد الممكن mod 6 لعدد أولي أكبر من 3 هو 1 و 5. لذا، فإن اختبار الأعداد الأولية الأكثر كفاءة لـ هو اختبار ما إذا كان قابلاً للقسمة على 2 أو 3، ثم التحقق من جميع الأعداد على هيئة و والتي تكون . وهذا أسرع بثلاث مرات تقريبًا من اختبار جميع الأعداد حتى . ${\displaystyle 6k+i}$${\displaystyle k}$${\displaystyle i\in \{1,5\}}$${\displaystyle 6k+i}$${\displaystyle k}$${\displaystyle i\in \{0,1,2,3,4,5\}}$${\displaystyle 6k,6k+2}$${\displaystyle 6k+4}$${\displaystyle 6k}$${\displaystyle 6k+3}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 6k+1}$${\displaystyle 6k+5}$${\displaystyle \leq {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$

وبتعميم أكبر، فإن جميع الأعداد الأولية الأكبر من ( الأساسية c ) تكون على هيئة الأعداد الصحيحة الموجبة، و، وأولية مشتركة لـ . على سبيل المثال، ضع في اعتبارك . جميع الأعداد الصحيحة تكون على هيئة الأعداد الصحيحة التي بها . الآن، 2 تقسم ، و3 تقسم ، و5 تقسم . وبالتالي فإن جميع الأعداد الأولية الأكبر من 30 تكون على هيئة . بالطبع، ليست كل الأعداد التي تكون على هيئة أولية مشتركة لـ تكون أولية. على سبيل المثال، ليس أوليًا، على الرغم من أن 17 أولي مشترك لـ . ${\displaystyle c\#}$${\displaystyle c\#\cdot k+i}$${\displaystyle i,k}$${\displaystyle 0\leq i<c\#}$${\displaystyle i}$ ${\displaystyle c\#}$${\displaystyle 6\#=2\cdot 3\cdot 5=30}$${\displaystyle 30k+i}$${\displaystyle i,k}$${\displaystyle 0\leq i<30}$${\displaystyle 0,2,4,\dots ,28}$${\displaystyle 0,3,6,\dots ,27}$${\displaystyle 0,5,10,\dots ,25}$${\displaystyle 30k+i}$${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$${\displaystyle c\#\cdot k+i}$${\displaystyle i}$${\displaystyle c\#}$${\displaystyle 19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17}$${\displaystyle 7\#=2\cdot 3\cdot 5\cdot 7}$

مع النمو، تقل نسبة باقي الأعداد الأولية المشتركة إلى الباقي، وبالتالي يقل وقت الاختبار (على الرغم من أنه لا يزال من الضروري التحقق من قابلية القسمة على جميع الأعداد الأولية التي تقل عن ). يمكن تطبيق الملاحظات المشابهة للملاحظات السابقة بشكل متكرر ، مما يعطي منخل إراتوستينس . ${\displaystyle c}$${\displaystyle n}$${\displaystyle c}$

إحدى الطرق لتسريع هذه الطرق (وكل الطرق الأخرى المذكورة أدناه) هي الحساب المسبق وتخزين قائمة بجميع الأعداد الأولية حتى حد معين، مثل جميع الأعداد الأولية حتى 200. (يمكن حساب مثل هذه القائمة باستخدام غربال إراتوستينس أو عن طريق خوارزمية تختبر كل زيادة مقابل جميع الأعداد الأولية المعروفة ). ثم، قبل اختبار الأعداد الأولية باستخدام طريقة واسعة النطاق، يمكن أولاً التحقق من قابلية القسمة على أي عدد أولي من القائمة. إذا كان قابلاً للقسمة على أي من هذه الأرقام، فهو مركب، ويمكن تخطي أي اختبارات أخرى. ${\displaystyle م}$${\displaystyle \leq {\sqrt {m}}}$${\displaystyle n}$${\displaystyle n}$

اختبار بسيط ولكن غير فعال للغاية للأعداد الأولية يستخدم نظرية ويلسون ، والتي تنص على أن يكون أوليًا إذا وفقط إذا: ${\displaystyle p}$

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

على الرغم من أن هذه الطريقة تتطلب عمليات ضرب معيارية، مما يجعلها غير عملية، فإن النظريات حول الأعداد الأولية والبقايا المعيارية تشكل الأساس للعديد من الطرق العملية الأخرى. ${\displaystyle p}$

هذه اختبارات تبدو فعالة في الممارسة العملية، لكنها غير مثبتة وبالتالي فهي ليست خوارزميات على الإطلاق من الناحية الفنية. اختبار فيرما واختبار فيبوناتشي هما مثالان بسيطان، وهما فعالان للغاية عند دمجهما. افترض جون سيلفريدج أنه إذا كان p عددًا فرديًا، و p ≡ ±2 (mod 5)، فإن p سيكون عددًا أوليًا إذا تحققت الشرطان التاليان:

• 2 ^{ص −1} ≡ 1 (تعديل ص )،
• f _{p +1} ≡ 0 (mod p )،

حيث f _k هو عدد فيبوناتشي k . الشرط الأول هو اختبار بدائية فيرما باستخدام القاعدة 2.

بشكل عام، إذا كان p ≡ a (mod x ² +4)، حيث a هي عدد غير متبقي تربيعي (mod x ² +4)، فيجب أن يكون p أوليًا إذا تحققت الشروط التالية:

• 2 ^{ص −1} ≡ 1 (تعديل ص )،
• f ( 1 ) _{p +1} ≡ 0 (mod p )،

f ( x ) _k هي متعددة حدود فيبوناتشي ذات الترتيب k عند x .

يقدم سيلفريدج وكارل بوميرانس وصامويل واجستاف معًا 620 دولارًا أمريكيًا لمثال مضاد. ^[2]

الاختبارات الاحتمالية أكثر صرامة من الاستدلالات لأنها توفر حدودًا يمكن إثباتها لاحتمالية التعرض للخداع من قبل عدد مركب. العديد من اختبارات البدائية الشائعة هي اختبارات احتمالية. تستخدم هذه الاختبارات، بصرف النظر عن العدد المختبر n ، بعض الأرقام الأخرى a التي يتم اختيارها عشوائيًا من بعض مساحة العينة ؛ لا تبلغ اختبارات البدائية العشوائية المعتادة عن عدد أولي على أنه مركب، ولكن من الممكن الإبلاغ عن عدد مركب على أنه أولي. يمكن تقليل احتمال الخطأ عن طريق تكرار الاختبار بعدة قيم مختارة بشكل مستقل من a ؛ بالنسبة لاختبارين شائعي الاستخدام، لأي مركب n على الأقل نصف a ' s اكتشف مركب n ' s، لذلك تقلل k تكرارات من احتمال الخطأ إلى 2 ^{− k} على الأكثر ، والذي يمكن جعله صغيرًا بشكل تعسفي عن طريق زيادة k .

البنية الأساسية لاختبارات البدائية العشوائية هي كما يلي:

1. إختر رقم عشوائيا .
2. تحقق من المساواة (المقابلة للاختبار المختار) التي تتضمن a والعدد المعطى n . إذا فشلت المساواة في أن تكون صحيحة، فإن n هو عدد مركب و a هو شاهد على المركب، ويتوقف الاختبار.
3. عد إلى الخطوة الأولى حتى تصل إلى الدقة المطلوبة.

بعد تكرار واحد أو أكثر، إذا لم يتم العثور على n كعدد مركب، فيمكن إعلانه على أنه أولي على الأرجح .

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

^إذا كان لدينا عدد صحيح n ، اختر عددًا صحيحًا أوليًا مشتركًا مع n واحسب n ^{− 1} modulo n . إذا كانت النتيجة مختلفة عن 1، فإن n تكون مركبة. إذا كانت 1، فإن n قد تكون أولية.

إذا كان n ⁻¹ (modulo n ) يساوي 1 لكن n ليس أوليًا، فإن n يُسمى عددًا أوليًا زائفًا على أساس a . في الممارسة العملية، إذا كان ⁿ −1 ⁽ modulo n ) يساوي 1، فإن ⁿ يكون عادةً أوليًا. ولكن إليك مثالًا مضادًا: إذا كان n = 341 و a = 2، فإن

${\displaystyle 2^{340}\equiv 1{\pmod {341}}}$

على الرغم من أن 341 = 11·31 مركب. في الواقع، 341 هو أصغر عدد أولي زائف ذو قاعدة 2 (انظر الشكل 1 من ^[3] ).

هناك فقط 21853 عددا أوليا زائفا من القاعدة 2 التي تكون أقل من 2.5 × 10¹⁰ (انظر الصفحة 1005 من ^[3] ). وهذا يعني أنه بالنسبة لـ n حتى 2.5 × 10¹⁰ ، إذا كان 2 ^{n −1} (modulo n ) يساوي 1، فإن n يكون أوليًا، ما لم يكن n واحدًا من هذه الأعداد الأولية الزائفة البالغ عددها 21853.

تمتلك بعض الأعداد المركبة ( أعداد كارمايكل ) خاصية أن n ^{− 1} يساوي 1 (بمعدل n ) لكل a الذي يكون أوليًا مشتركًا مع n . وأصغر مثال على ذلك هو n = 561 = 3·11·17، حيث يكون 560 يساوي ¹ (بمعدل 561) لجميع الأعداد الأولية المشتركة مع 561. ومع ذلك، غالبًا ما يُستخدم اختبار فيرما ^إذا كانت هناك حاجة إلى فحص سريع للأرقام، على سبيل المثال في مرحلة توليد المفتاح لخوارزمية التشفير بالمفتاح العام RSA .

اختبار ميللر -رابين للبدائية واختبار سولوفاي-ستراسن للبدائية هما متغيران أكثر تطورًا، حيث يكشفان عن جميع المركبات (مرة أخرى، هذا يعني: لكل عدد مركب n ، على الأقل 3/4 (ميللر-رابين) أو 1/2 (سولوفاي-ستراسن) من الأرقام a هي شهود على مركبية n ). وهذه أيضًا اختبارات مركبة.

يعمل اختبار ميلر-رابين للبدائية على النحو التالي: إذا كان لدينا عدد صحيح n ، فاختر عددًا صحيحًا موجبًا a  <  n . ليكن 2 ^s d = n  − 1، حيث d عدد فردي. إذا كان

${\displaystyle a^{d}\not \equiv \pm 1{\pmod {n}}}$

و

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$للجميع${\displaystyle 0\leq r\leq s-1,}$

عندئذٍ يكون n مركبًا ويكون a شاهدًا على المركبية. وإلا، فقد يكون n أوليًا أو لا يكون. اختبار ميلر-رابين هو اختبار أولي محتمل قوي (انظر PSW ^[3] الصفحة 1004).

يستخدم اختبار بدائية سولوفاي-ستراسن مساواة أخرى: إذا كان لدينا عدد فردي n ، فاختر عددًا صحيحًا a  <  n ، إذا كان

${\displaystyle a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}}$أين رمز جاكوبي ؟${\displaystyle \left({\frac {a}{n}}\right)}$

عندئذٍ يكون n مركبًا ويكون a شاهدًا على المركبية. وإلا، فقد يكون n أوليًا أو لا يكون. اختبار سولوفاي-ستراسن هو اختبار أولي محتمل لأويلر (انظر PSW ^[3] الصفحة 1003).

بالنسبة لكل قيمة فردية لـ a ، يكون اختبار Solovay-Strassen أضعف من اختبار Miller-Rabin. على سبيل المثال، إذا كان n = 1905 و a = 2، فإن اختبار Miller-Rabin يُظهر أن n مركب، لكن اختبار Solovay-Strassen لا يفعل ذلك. وذلك لأن 1905 عبارة عن عدد أولي زائف أويلر ذو قاعدة 2 ولكنه ليس عدد أولي زائف قوي ذو قاعدة 2 (يتضح هذا في الشكل 1 من PSW ^[3] ).

اختبارات ميللر-رابين وسولوفاي-ستراسن للبدائل بسيطة وأسرع بكثير من اختبارات البدائل العامة الأخرى. إحدى الطرق لتحسين الكفاءة بشكل أكبر في بعض الحالات هي اختبار شبه البدائل لفروبينيوس ؛ تستغرق جولة من هذا الاختبار حوالي ثلاثة أضعاف الوقت الذي تستغرقه جولة ميللر-رابين، لكنها تحقق حد احتمال مماثل لسبع جولات من ميللر-رابين.

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

اختبار الأعداد الأولية لبيللي-بي إس دبليو هو اختبار احتمالي للأعداد الأولية يجمع بين اختبار فيرما أو ميللر-رابين واختبار الأعداد الأولية المحتملة للوكاس للحصول على اختبار للأعداد الأولية ليس له أمثلة مضادة معروفة. أي أنه لا توجد أعداد مركبة معروفة n والتي يشير هذا الاختبار إلى أن n ربما تكون أولية. ^{[4] [5]} وقد ثبت أنه لا توجد أمثلة مضادة لـ n . ${\displaystyle <2^{64}}$

قدم ليونارد أدلمان ومينج دي هوانج نسخة خالية من الأخطاء (ولكن متوقعة في زمن متعدد الحدود) من اختبار الأعداد الأولية للمنحنى الإهليلجي . وعلى عكس الاختبارات الاحتمالية الأخرى، تنتج هذه الخوارزمية شهادة الأعداد الأولية ، وبالتالي يمكن استخدامها لإثبات أن الرقم أولي. ^[6] الخوارزمية بطيئة للغاية في الممارسة العملية.

إذا كانت أجهزة الكمبيوتر الكمومية متاحة، فيمكن اختبار البدائية بشكل أسرع من استخدام أجهزة الكمبيوتر الكلاسيكية. يمكن حل المشكلة عن طريق الجمع بين خوارزمية شور ، وهي طريقة تحليل العوامل الصحيحة، مع اختبار البدائية بوكلينجتون . ^[7]${\displaystyle O((\log n)^{3}(\log \log n)^{2}\log \log \log n)}$

في بداية القرن العشرين تقريبًا، تم إثبات أنه يمكن استخدام نتيجة تكميلية لنظرية فيرما الصغيرة لاختبار البدائية. ^[8] أدى هذا إلى اختبار بدائية بوكلينجتون . ^{[9] ومع ذلك، نظرًا لأن هذا الاختبار يتطلب} تحليل جزئي لعوامل n  − 1، كان وقت التشغيل لا يزال بطيئًا جدًا في أسوأ الحالات. كان أول اختبار بدائية حتمي أسرع بكثير من الطرق الساذجة هو اختبار السيكلوتومي ؛ يمكن إثبات أن وقت تشغيله هو O ((log  n ) ^{c  log log log  n} )، حيث n هو الرقم الذي يجب اختبار البدائية و c ثابت مستقل عن n . تم إجراء العديد من التحسينات الأخرى، ولكن لم يتم إثبات أن أيًا منها له وقت تشغيل متعدد الحدود. (يتم قياس وقت التشغيل من حيث حجم المدخلات، والذي في هذه الحالة هو ~ log  n ، وهو عدد البتات اللازمة لتمثيل الرقم n .) يمكن إثبات أن  اختبار بدائية المنحنى الإهليلجي يعمل في O((log n ) ⁶ )، إذا كانت بعض التخمينات حول نظرية الأعداد التحليلية صحيحة. ^{[ أيهما؟ ]} وبالمثل، بموجب فرضية ريمان المعممة ، يمكن إثبات أن اختبار ميلر الحتمي ، الذي يشكل أساس اختبار ميلر-رابين الاحتمالي، يعمل في Õ ((log  n ) ⁴ ). ^[10] في الممارسة العملية، تكون هذه الخوارزمية أبطأ من الخوارزميتين الأخريين بالنسبة لأحجام الأرقام التي يمكن التعامل معها على الإطلاق. نظرًا لأن تنفيذ هاتين الطريقتين صعب إلى حد ما ويخلق خطر حدوث أخطاء في البرمجة، فغالبًا ما تكون الاختبارات الأبطأ ولكن الأبسط مفضلة.

في عام 2002، اخترع مانيندرا أجراوال ونيراج كايال ونيتين ساكسينا أول اختبار زمني متعدد الحدود حتمي غير مشروط يمكن إثباته للبدائية . يعمل اختبار البدائية AKS في Õ((log  n ) ¹² ) (تم تحسينه إلى Õ((log  n ) ^7.5 ) ^[11] في المراجعة المنشورة لورقتهم)، والتي يمكن تقليصها إلى Õ((log  n ) ⁶ ) إذا كان تخمين صوفي جيرمان صحيحًا. ^[12] بعد ذلك، قدم لينسترا وبوميرانس نسخة من الاختبار تعمل في الوقت Õ((log  n ) ⁶ ) دون قيد أو شرط. ^[13]

يقترح أجراوال وكايال وساكسينا متغيرًا من خوارزميتهم والذي سيتم تشغيله في Õ((log  n ) ³ ) إذا كان تخمين أجراوال صحيحًا؛ ومع ذلك، تشير الحجة الاستدلالية التي قدمها هندريك لينسترا وكارل بوميرانس إلى أنه ربما يكون خاطئًا. ^[11] قد لا تزال النسخة المعدلة من تخمين أجراوال، تخمين أجراوال-بوبوفيتش، ^[14] صحيحة.

في نظرية التعقيد الحسابي ، يتم الإشارة إلى اللغة الرسمية المقابلة للأعداد الأولية باسم PRIMES. من السهل إظهار أن PRIMES في Co-NP : مكملها COMPOSITES في NP لأنه يمكن للمرء أن يقرر التركيب من خلال تخمين عامل بشكل غير حتمي.

في عام 1975، أظهر فوغان برات وجود شهادة للأولية يمكن التحقق منها في زمن متعدد الحدود، وبالتالي فإن الأعداد الأولية كانت في NP ، وبالتالي في ⁠ ⁠${\displaystyle {\mathsf {NP\cap coNP}}}$ . راجع شهادة الأولية للحصول على التفاصيل.

أدى الاكتشاف اللاحق لخوارزميات Solovay-Strassen وMiller-Rabin إلى وضع الأعداد الأولية في coRP . في عام 1992، قللت خوارزمية Adleman-Huang ^[6] التعقيد إلى ⁠ ⁠${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$ ، والتي حلت محل نتيجة Pratt.

وضع اختبار الأعداد الأولية Adleman–Pomerance–Rumely لعام 1983 الأعداد الأولية في QP ( زمن شبه متعدد الحدود )، والذي لا يُعرف أنه قابل للمقارنة مع الفئات المذكورة أعلاه.

نظرًا لسهولة التعامل معه في الممارسة العملية، فإن خوارزميات زمن كثير الحدود التي تفترض فرضية ريمان، وغيرها من الأدلة المماثلة، كانت تشك لفترة طويلة في إمكانية حل الأعداد الأولية في زمن كثير الحدود ولكن لم يتم إثبات ذلك. أدى وجود اختبار الأعداد الأولية AKS إلى تسوية هذا السؤال الطويل الأمد ووضع الأعداد الأولية في P. ومع ذلك، لا يُعرف أن الأعداد الأولية مكتملة P ، ولا يُعرف ما إذا كانت تقع في فئات تقع داخل P مثل NC أو L. ومن المعروف أن الأعداد الأولية ليست في AC ^0. [ 15 ^]

توجد طرق نظرية عددية معينة لاختبار ما إذا كان الرقم أوليًا، مثل اختبار لوكاس واختبار بروث . تتطلب هذه الاختبارات عادةً تحليل n  + 1 أو n − 1 أو كمية مماثلة إلى عوامل، مما يعني أنها ليست مفيدة لاختبار الأعداد الأولية للأغراض العامة، لكنها غالبًا ما تكون قوية جدًا عندما يكون من المعروف أن الرقم المختبر n له شكل خاص.

يعتمد اختبار لوكاس على حقيقة أن الترتيب المضاعف للعدد a modulo n هو n − 1 لعدد أولي n عندما يكون a جذرًا بدائيًا modulo n . إذا تمكنا من إظهار أن a بدائي بالنسبة لـ n ، فيمكننا إظهار أن n أولي.

• Solovay-Strassen (computacion.cs.cinvestav.mx) at archive.today (تم أرشفته في 2012-12-20) – تنفيذ اختبار بدائية Solovay-Strassen في Maple
• التمييز بين الأعداد الأولية والأعداد المركبة، بقلم دي جي بيرنشتاين (cr.yp.to)
• الصفحات الرئيسية (primes.utm.edu)
• اختبار لوكاس للأعداد الأولية مع تحليل N − 1 (MathPages.com) في أرشيفات الويب الخاصة بمكتبة الكونجرس (تم أرشفته في 2010-08-06)
• PRIMABOINCA هو مشروع بحثي يستخدم أجهزة كمبيوتر متصلة بالإنترنت للبحث عن مثال مضاد لبعض التخمينات. كان التخمين الأول ( تخمين أجراوال ) هو الأساس لصياغة أول خوارزمية اختبار أولية حتمية في زمن متعدد الحدود ( خوارزمية AKS ).