مدقق البدائية

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

بالنسبة للأعداد التي تقل عن 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 - المربع والضرب، مما يقلل من modulo n في كل خطوة حتى لا تنفجر الأرقام أبدًا - شيئًا فشيئًا للشاهد الأول، ويبلغ عن حكم كل شاهد، بما في ذلك الشاهد الذي يثبت التركيب إذا تبين أن الرقم ليس أوليًا. كل شيء يعمل محليًا في متصفحك: لا يوجد خادم، ولا واجهة برمجة تطبيقات خارجية، ولا توجد بيانات تخرج من جهازك على الإطلاق.