فاحص أعداد فيرما شبه الأولية لأي أساس

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

ما الذي تعنيه نتيجة الاجتياز فعلياً

تنص مبرهنة فيرما الصغرى على أنه إذا كان n عدداً أولياً ولم يكن a قابلاً للقسمة على n، فإن باقي a مرفوعاً إلى القوة n ناقص واحد بترديد n يساوي واحداً. لكن العكس غير مضمون. فبعض الأعداد الصحيحة المركبة تعطي أيضاً الباقي واحداً عند أسس معينة، وتسمى أعداد فيرما شبه الأولية بالنسبة إلى تلك الأسس. يشترط هذا الفاحص عمداً أن يكون n مركباً، ويتحقق من هذا الشرط أولاً، ثم يقيم علاقة التطابق حسابياً بدقة. عندما تكون passes_fermat_test وis_fermat_pseudoprime صحيحتين، فهذا يعني أن العدد المركب المدخل خدع اختبار فيرما عند ذلك الأساس تحديداً. ولا يعني أن n أولي أو أولي محتمل أو شبه أولي عند كل أساس. فالأساس جزء من الحكم، وينبغي أن يرافق النتيجة دائماً. ويوفر الباقي المعاد الدليل الحسابي المباشر: الواحد يعني الاجتياز، وأي قيمة أخرى تعني الإخفاق. كما يفيد القاسم المشترك الأكبر في تمييز التجارب ذات الأساس الأولي نسبياً عن المدخلات التي تكشف منذ البداية علاقة عامل غير تافهة.

كيف يحافظ الحساب على الدقة

يدخل العددان كسلسلتين عشريتين حتى لا تقرب الأعداد الصحيحة الأكبر من المجال العددي الآمن في JavaScript قبل إجراء الحساب. وينتهي المجال المقبول عند أكبر عدد صحيح غير موقع من 64 بت، مما يمنح فحص الأولية حداً واضحاً قابلاً للإنفاذ. قبل تنفيذ اختبار فيرما، يستخدم الفاحص إجراء Miller–Rabin حتمياً مع مجموعة شواهد كافية للمجال كله. وإذا اكتشف أن العدد أولي، فإنه يعيد خطأ في الإدخال، لأن الأعداد الأولية تحقق المبرهنة لكنها لا تعد أعداداً شبه أولية بحكم التعريف. وللعدد المركب الصحيح، يستخدم الرفع النمطي طريقة التربيع المتكرر بدلاً من إنشاء القيمة الهائلة a^(n-1). وتختزل كل عملية ضرب بترديد n، فتبقى القيم الوسيطة محدودة ودقيقة باستخدام BigInt. وتحسب خوارزمية إقليدس gcd(a,n) بصورة مستقلة. ويجب أن يحقق الأساس الشرط 2 <= a <= n - 2. لا تؤثر شواهد عشوائية أو أوقات أو اتصالات شبكة أو عمليات فاصلة عائمة في الجواب، لذلك تنتج المدخلات المتطابقة مخرجات متطابقة دائماً.

استخدام الفاحص في التعلم والتحقق

من الأمثلة التقليدية n = 341 مع الأساس a = 2. فالعدد 341 مركب، لكن 2^340 يطابق واحداً بترديد 341، ولذلك يجتاز الاختبار ويكون شبه أولي لفيرما عند الأساس اثنين. وإذا تغير الأساس فقد يخفق العدد المركب نفسه، ولهذا لا يمثل اختبار فيرما الواحد شهادة عامة على الأولية. في الدروس، تربط المخرجات المنظمة التعريف مباشرة بالباقي المحسوب. وفي حزمة اختبارات برمجية، يمكن حفظ حالات معروفة لأعداد شبه أولية وأعداد غير شبه أولية دون الاعتماد على مكتبة رياضية أو تحويلات عددية مرتبطة بجهاز معين. وللاستكشاف، قارن عدة أسس مسموحة مع إبقاء n ثابتاً لملاحظة أثر اختيار الشاهد. تعامل مع النتيجة الصحيحة بوصفها عرضاً لحدود اختبار فيرما، لا إذناً باعتبار العدد أولياً في الشيفرات التعمية أو الحساسة أمنياً. تبلغ كلفة API مقدار $0.002 لكل زوج مفحوص، بينما تنفذ نسخة المتصفح الحساب الحتمي نفسه محلياً.