اختبار أولية بروث باستخدام شاهد

أدخلوا عدد بروث صحيحاً وشاهداً

يأخذ عدد بروث الصورة الدقيقة N = k × 2^n + 1، حيث يكون k عدداً صحيحاً موجباً وفردياً، ويكون n عدداً صحيحاً موجباً، ويكون k أصغر قطعاً من 2^n. ولا يجوز إهمال أي شرط من هذه الشروط. تستقبل الحاسبة k والشاهد كنصين عشريين كي تبقى القيم الكبيرة دقيقة ولا تتعرض لتقريب الفاصلة العائمة. أدخلوا n كعدد صحيح من 1 إلى 10,000. تنشئ الأداة N من المعلمات بدلاً من طلبه منفصلاً، وبذلك تمنع التعارض بين العدد المعلن والمعلمات التي تعرفه. كما تتحقق من وقوع الشاهد بين 1 وN حصراً. إذا كان k زوجياً، أو كانت قيمة ما غير موجبة، أو كان k أكبر من 2^n أو مساوياً له، ترفض الأداة الإدخال لأنه ليس من صيغة بروث، فلا تطبق مبرهنة خارج شروطها. وتعيد العدد والأس والشاهد والباقي كسلاسل عشرية عند الحاجة، مما يتيح لكم مراجعة الحساب ونسخ القيم إلى أداة أخرى تدعم الحساب الصحيح الدقيق دون فقدان.

افهموا ما يثبته التطابق

تنص مبرهنة بروث، لعدد بروث صحيح N، على أن N أولي إذا وجد عدد صحيح a بحيث تكون a^((N−1)/2) مطابقة مع −1 بترديد N. والشاهد الذي تقدمونه هو a. تحسب الأداة القوة المعيارية بالتربيع المتكرر من دون إنشاء القوة العادية الهائلة أولاً. في المخرجات، يمثل `residue` أصغر باق غير سالب، وتكون `passes_test` مساوية إلى true فقط عندما يساوي هذا الباقي N−1، وهو تمثيل −1 بترديد N. عندئذ تكون `prime_proven` مساوية إلى true ويكون الحكم `prime`. وبعد التحقق من شروط بروث، تكون هذه شهادة قطعية وليست تخميناً احتمالياً بأن العدد أولي. تتضمن النتيجة الأس الدقيق (N−1)/2 كي تتمكنوا من إعادة حساب التطابق بصورة مستقلة. لا تستخدم الخوارزمية إلا عمليات على أعداد صحيحة، ولا تختار شاهداً عشوائياً، ولا تستعلم من جدول أو خدمة بعيدة. لذلك يعطي الإدخال نفسه النتيجة نفسها دائماً، وتظهر في الإجابة كل القيم المهمة التي استخدمتها المبرهنة.

تعاملوا مع إخفاق الشاهد بصورة صحيحة

إذا لم ينتج الشاهد −1، فلا يثبت ذلك وحده أن العدد مركب. بل يعني فقط أن هذا الشاهد بعينه لم يحقق الشرط الكافي في مبرهنة بروث. ولهذا تعيد الأداة `inconclusive` بدلاً من `composite` عندما يختلف الباقي ويكون الشاهد أولياً نسبياً مع N. يمكنكم بعد ذلك تجربة شاهد آخر مختار وفق أساس رياضي أو استخدام طريقة قطعية أخرى لاختبار الأولية. وهناك استثناء مفيد: قبل تفسير التطابق، تحسب الأداة القاسم المشترك الأكبر بين الشاهد وN. فإذا كانت القيمة عاملاً حقيقياً، أصبحت النتيجة القطعية `composite` وأعيد العامل أيضاً. يمنع هذا التفريق الخطأ الشائع المتمثل في تحويل مبرهنة ذات اتجاه واحد إلى اختبار ثنائي الاتجاه غير صحيح. كما يفيد في سير العمل الآلي: اقبلوا `prime` بوصفه برهاناً، وارفضوا `composite` عند ظهور عامل، ووجّهوا `inconclusive` إلى اختبار آخر بدلاً من اعتباره بصمت إخفاقاً نهائياً.