مُختبر الأولية

يُخبرك مُختبر الأولية إن كان العدد الصحيح أوليًا، وعلى عكس معظم الأدوات المتاحة إلكترونيًا، فإنه يريك الخوارزمية الفعلية التي أثبتت ذلك، وليس مجرد جدول بحث مُخزّن. أدخل أي عدد صحيح، موجبًا أو سالبًا، صغيرًا أو هائلًا، لتُقرر الأداة أي خوارزمية حقيقية ستشغلها بناءً على حجمه.

للأعداد تحت 10¹² (ترليون)، تُنفذ الأداة قسمة تجريبية حقيقية: تبدأ من 2، وتُجرّب كل عدد صحيح مُرشح حتى الجزء الصحيح من n√ كقاسم مُحتمل، وتتوقف لحظة أن ينقسم أحدها تمامًا (مُركّب) أو تؤكد أنه لا يوجد أي قاسم بعد أن فُحص كل مُرشح حتى n√ (أولي). عندما يكون عدد المُرشحين ضخمًا، يقتصر التتبع على أول 18 عدد تقريبًا بالإضافة إلى الأخير، مع ملاحظة صادقة بعدد ما تم تخطيه في العرض — لكن كل مُرشح لا يزال يُفحص فعليًا بواسطة الكود، ولا يتم تخطي أيٍ منها في الحوسبة.

للأعداد عند هذا الحد أو فوقه — وهو نطاق الحجم المُستخدم في التشفير — ستستغرق القسمة التجريبية وقتًا طويلًا جدًا، لذلك تنتقل الأداة إلى اختبار ميلر-رابين للأولية بمجموعة قطعية ثابتة من 13 شاهدًا أوليًا (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). مجموعة الشهود هذه هي نتيجة معروفة: لا تملك أي نتائج إيجابية خاطئة لأي n أقل من 3,317,044,064,679,887,385,961,981 (حوالي 3.3×10²⁴)، وهو حد أُثبت بالتحقق الحوسبي (انظر Sorenson & Webster, 2015، وجدول الشهود القطعية المُعاد نشره على نطاق واسع الذي تنتمي إليه). فوق هذا الحد، لا يزال الاختبار نفسه يعمل، لكن الأداة تخبرك بأمانة أن الضمان يتحول إلى ضمان احتمالي قوي للغاية بدلًا من اليقين الرياضي.

يكتب تتبع اختبار ميلر-رابين n − 1 = 2ˢ × d حيث d فردي، ثم يسير عبر الأس المعياري الحقيقي باستخدام BigInt — يربع ثم يضرب، مع اختزال بقياس n في كل خطوة حتى لا تنفجر الأعداد — بتة بتة للشاهد الأول، ويُبلغ بحكم كل شاهد، بما في ذلك الشاهد الذي يُثبت التركيب إن تبين أن العدد ليس أوليًا. كل شيء يعمل محليًا في متصفحك: لا خادم، ولا API خارجية، ولا تغادر أي بيانات جهازك أبدًا.