كيفية إجراء اختبار فيرمات للبدائية في أقل من 3 دقائق

يعتمد اختبار فيرمات على نتيجة من نظرية الأعداد المعروفة باسم نظرية فيرما الصغيرة.

وفقًا لنظرية فيرما الصغيرة ، إذا كان n عددًا أوليًا وكان d أي عدد صحيح موجب أقل من n ، فإن d المرفوع للقوة n يكون مطابقًا لـ d modulo n .

إذا رقمين لديهم نفس الباقي عندما مقسوما ن ثم قالوا ليكون مودولو المنسجمة ن . d modulo n هو ببساطة باقي الرقم d عند القسمة على n .

على سبيل المثال ، 34 مطابق لـ 16 (modulo 3) مثل

34 modulo 3 = 1 و 16 modulo 3 = 1.

اختبار فيرمات للبدائية

  1. بالنسبة لرقم معين n ، اختر عددًا عشوائيًا موجبًا d بحيث يكون d < ؛ ن.
  2. احسب (d ^ n) modulo n .
  3. سيكون d modulo n دائمًا d لأننا دائمًا نختار d الذي يفي بالشرط d < ؛ ن.
  4. إذا كانت نتيجة (d ^ n) modulo n لا تساوي d ، فإن d بالتأكيد ليست أولية.
  5. إذا كانت نتيجة (d ^ n) modulo n تساوي d ، فمن المحتمل أن يكون n عددًا أوليًا.
  6. اختر d عشوائيًا آخر يفي بالشرط d < n وكرر الخطوات المذكورة أعلاه.

ملاحظة : تستخدم الأمثلة في هذا المنشور Swift 4.1

نحتاج إلى دالة لحساب الأسي لعدد من الوحدات النمطية لرقم آخر.

نستخدم الأس المعياري لحساب القيم عندما يكون الأس أكبر من 1 لأن هذا يتيح لنا إجراء الحساب أثناء التعامل فقط مع الأرقام الأقل من n ( modulo في الوظيفة أعلاه).

يختار اختبار Fermat عشوائيًا عددًا d بين 1 و n-1 ( الرقم - 1 في الوظيفة أعلاه) ضمناً. الهدف هو التحقق مما إذا كان باقي المقياس n للقوة n لـ d يساوي d.

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

من خلال تجربة المزيد والمزيد من قيم d (رقم موجب عشوائي بين 1 و n-1) ، يمكننا زيادة ثقتنا في النتيجة.