اختبار الأسبقية

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

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

على سبيل المثال، لنأخذ العدد 100، الذي قواسمه هي هذه الأعداد:

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

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

${\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}$.

المنتجات السابقة${\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}}}$لضمان اكتشاف جميع أزواج القواسم. ^{[ 1 ]}

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

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

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

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

وبالتعميم أكثر، فإن جميع الأعداد الأولية الأكبر من${\displaystyle p_{m}}$(ال${\displaystyle m}$(العدد الأولي رقم n) تكون على الشكل${\displaystyle p_{m}\#\cdot k+i}$، أين${\displaystyle \{k,i\in \mathbb {Z} \mid 0\leq i<p_{m}\#\land {\text{gcd}}\left(p_{m}\#,i\right)=1\}}$و${\displaystyle p_{m}\#}$هو الأصل – نتاج الأول${\displaystyle m}$الأعداد الأولية.

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

بينما${\displaystyle \lim _{m\to \infty }{\frac {\phi \left(p_{m}\#\right)}{p_{m}\#}}=0}$، أين${\displaystyle \phi \left(m\right)}$هي دالة أويلر ، التي تتحقق من قابلية القسمة على جميع الأعداد الأولية الأصغر من${\displaystyle p_{m}\#}$لا تزال هناك حاجة إلى ذلك. يمكن تطبيق الملاحظات المماثلة لما سبق بشكل متكرر ، مما يعطي منخل إراتوستينس .

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

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

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

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

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

• 2p ⁻¹ ≡ 1 (mod ^p ) ,
• f _{p +1} ≡ 0 (mod p ),

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

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

• 2p ⁻¹ ≡ 1 (mod ^p ) ,
• f ( x ) _{p +1} ≡ 0 (mod p ),

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

عرضت سيلفريدج وبوميرانس وواغستاف معًا 620 دولارًا مقابل مثال مضاد أو دليل على عدم وجوده، ^{[ 3 ]} مع استحقاق الجائزة الآن من مؤسسة نظرية الأعداد .

تُعدّ الاختبارات الاحتمالية أكثر دقة من الطرق الاستدلالية، إذ تُقدّم حدودًا قابلة للإثبات لاحتمالية الخطأ في تحديد عدد مُركّب. العديد من اختبارات أولية الأعداد الشائعة هي اختبارات احتمالية. تستخدم هذه الاختبارات، بالإضافة إلى العدد المُختَبَر n ، أعدادًا أخرى a تُختار عشوائيًا من فضاء عينة . لا تُشير اختبارات أولية الأعداد العشوائية المعتادة إلى أن عددًا أوليًا مُركّب، ولكن من الممكن أن يُصنّف عدد مُركّب على أنه أولي. يُمكن تقليل احتمالية الخطأ بتكرار الاختبار باستخدام عدة قيم مُختارة بشكل مستقل لـ a . بالنسبة لاختبارين شائعي الاستخدام، لأي عدد مُركّب n، يكشف نصف قيم a على الأقل عن كون n مُركّبًا ، لذا فإن k تكرارًا يُقلّل احتمالية الخطأ إلى 2 ^{- k} على الأكثر ، والتي يُمكن تصغيرها بشكل تعسفي بزيادة k .

تتمثل البنية الأساسية لاختبارات أولية عشوائية فيما يلي:

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

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

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

في عام ٢٠٠٢، ابتكر مانيندرا أغراوال ، ونيراج كايال ، ونيتين ساكسينا أول اختبارٍ مُثبتٍ وغير مشروطٍ لتحديد أولية الأعداد في زمنٍ متعدد الحدود. يعمل اختبار AKS لأولية الأعداد في زمن Õ((log n ) ¹² ) (تم تحسينه إلى Õ((log n ) ^7.5 ) ^{[ ١٢ ]} في النسخة المنشورة من بحثهم)، والذي يمكن اختزاله إلى Õ((log n ) ⁶ ) إذا كانت فرضية صوفي جيرمان صحيحة. ^{[ ١٣ ]} لاحقًا، قدم لينسترا وبوميرانس نسخةً من الاختبار تعمل في زمن Õ((log n ) ⁶ ) بشكلٍ غير مشروط. ^{[ ١٤ ]}    

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

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

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

أدى اكتشاف خوارزميتي سولوفاي-ستراسن وميلر-رابين لاحقًا إلى دمج الأعداد الأولية في coRP . وفي عام 1992، قللت خوارزمية أدلمان-هوانغ ^{[ 7 ]} التعقيد إلى${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$، وهو ما تجاوز نتيجة برات.

وضع اختبار أدلمان -بوميرانس-روميلي للأعداد الأولية من عام 1983 الأعداد الأولية في QP ( الوقت شبه متعدد الحدود )، والذي من غير المعروف أنه قابل للمقارنة مع الفئات المذكورة أعلاه.

بسبب سهولة تطبيقها عمليًا، وخوارزمياتها التي تعمل في زمن متعدد الحدود بافتراض فرضية ريمان، وغيرها من الأدلة المشابهة، كان يُشتبه لفترة طويلة، وإن لم يُثبت، بإمكانية حل مسألة الأعداد الأولية في زمن متعدد الحدود. وقد حسم وجود اختبار AKS للأعداد الأولية هذا السؤال العالق، ووضع مجموعة الأعداد الأولية (PRIMES) ضمن المجموعة P. مع ذلك، لا يُعرف ما إذا كانت PRIMES مجموعة كاملة بالنسبة لـ P ، ولا يُعرف ما إذا كانت تنتمي إلى فئات تقع داخل ^P مثل NC أو L. ومن المعروف أن PRIMES لا تنتمي إلى AC0 ^. [ ^{16 ]}

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

يعتمد اختبار لوكاس على حقيقة أن الرتبة الضربية للعدد a بتردد n تساوي n - 1 عندما يكون n عددًا أوليًا ، وذلك عندما يكون a جذرًا أوليًا بتردد n . إذا استطعنا إثبات أن a عدد أولي بالنسبة لـ n ، فسنتمكن من إثبات أن n عدد أولي.

• رابط قديم على archive.today (تمت أرشفته في 20 ديسمبر 2012) - تطبيق اختبار سولوفاي-ستراسن للأعداد الأولية في مابل
• التمييز بين الأعداد الأولية والأعداد المركبة، بقلم دي جيه بيرنشتاين (cr.yp.to)
• الصفحات الرئيسية (primes.utm.edu)
• اختبار لوكاس الأولي مع N  −  1 المُعامل (MathPages.com) في أرشيفات الويب لمكتبة الكونغرس (تمت أرشفته في 2010-08-06)
• مشروع PRIMABOINCA هو مشروع بحثي يستخدم أجهزة كمبيوتر متصلة بالإنترنت للبحث عن مثال مضاد لبعض الفرضيات. وكانت الفرضية الأولى ( فرضية أغراوال ) أساسًا لصياغة أول خوارزمية اختبار أولية حتمية في وقت متعدد الحدود ( خوارزمية AKS ).