التحقق من الأعداد الأولية

كيفية استخدام أداة التحقق من الأعداد الأولية

1. اكتب عدد صحيح. وتُقبل التعابير الحسابية أيضًا: 2^61-1 أو 10^12+39 أو 20!+1 أو 3711.
2. يظهر الجواب أثناء الكتابة؛ واضغط تحقّق لمنح التحليل وقتًا أطول مع الأعداد الصعبة.
3. اقرأ الحكم، ثم التحليل إلى عوامل أولية، وعدد القواسم، والعدد الأولي السابق، والعدد الأولي التالي. تشرح لوحة لماذا كيف توصّلت الأداة إلى الجواب، وينسخ زر نسخ التحليل حاصل ضرب العوامل الأولية.
4. لعرض قائمة بالأعداد الأولية، املأ الحقلين من وإلى في قسم الأعداد الأولية في مجال، ثم اضغط اعرض الأعداد الأولية.

تُقبل الأعداد حتى 2048 بت (نحو 617 رقمًا)، ويجري كل شيء داخل متصفحك.

متى يكون العدد أوليًا؟

العدد الأولي عدد صحيح أكبر من 1 لا يقبل القسمة إلا على 1 وعلى نفسه: 2، 3، 5، 7، 11، 13… أما العدد الذي له قواسم أخرى فهو عدد مركّب، ويمكن كتابته بطريقة واحدة فقط على شكل حاصل ضرب أعداد أولية، وهذا هو تحليله إلى عوامل أولية (360 = 2³ × 3² × 5). والعددان 0 و1 ليسا أوليين ولا مركّبين، و2 هو العدد الأولي الزوجي الوحيد.

ويُستنتج عدد القواسم من التحليل: أضف 1 إلى كل أسّ ثم اضرب النتائج. فالعدد 360 = 2³ × 3² × 5 له (3 + 1)(2 + 1)(1 + 1) = 24 قاسمًا. أما العدد الأولي فله قاسمان دائمًا.

كيف يعمل الاختبار؟

• الأعداد الصغيرة (أقل من مليون) تُفحص بالقسمة التجريبية: إن لم يقسم العددَ أيُّ عدد أولي حتى جذره التربيعي، فهو أولي. ولا حاجة إلى تجاوز ذلك، لأن العدد المركّب له دائمًا عامل لا يزيد على جذره التربيعي.
• الأعداد الأكبر تُقسم أولًا على كل الأعداد الأولية الأصغر من 1000، ثم تخضع لاختبار ميلر–رابين. ومع الأسس الثلاثة عشر 2، 3، 5، …، 41، ثبت أن هذا الاختبار دقيق لكل عدد أصغر من 3.3 × 10²⁴، وهذا يشمل كل الأعداد الصحيحة ذات 64 بت. فالجواب بالنسبة إلى هذه الأعداد مؤكد.
• فوق 3.3 × 10²⁴ تُستخدم 25 أساسًا، والعدد الذي ينجح فيها كلها يوصف بأنه أولي على الأرجح. احتمال الخطأ أقل من 1 من 10¹⁵، لكنه ليس برهانًا رياضيًا. أما إذا فشل الاختبار فالعدد مركّب حتمًا.

كيف تُحلَّل الأعداد؟

تُكتشف العوامل الصغيرة بالقسمة التجريبية. أما الأجزاء المركّبة الأكبر فتُفكك بخوارزمية رو لبولارد (Pollard’s rho، بصيغة Brent)، التي تجد عوامل تصل إلى نحو 10 أرقام في جزء من الثانية. والأعداد الأصعب، كحاصل ضرب عددين أوليين من 15 رقمًا أو أكثر، قد تستغرق وقتًا يفوق أي مهلة، لذا يتوقف التحليل بعد بضع ثوانٍ. ويُعلَّم العامل الأخير حينها بأنه مركّب لم يُحلَّل، والضغط على تحقّق مجددًا يمنحه وقتًا إضافيًا.

الأعداد الأولية في مجال

تعتمد قائمة المجال على غربال إراتوستينس المقسّم إلى أجزاء، الذي يشطب مضاعفات كل عدد أولي. ويقبل حتى 1,000,000 عدد في المجال الواحد، مع حد أعلى يصل إلى 10¹². يشمل العدّ المجال كاملًا، وتُعرض أول 2,000 عدد أولي. فمثلًا، هناك 25 عددًا أوليًا بين 1 و100، و78,498 عددًا أوليًا أصغر من مليون.