حاسبة مبرهنة فيرما الصغرى مقدمة من Hesapstan لشرح التحقق من المبرهنة، واختزال القوى، وحساب المعكوس المعياري عندما يكون المعامل عددًا أوليًا.
مبرهنة فيرما الصغرى تصف نمط القوى عند القسمة على عدد أولي
تقول مبرهنة فيرما الصغرى إنه إذا كان p عددًا أوليًا وكان a متباينًا نسبيًا مع p، فإن a^(p−1) ≡ 1 (mod p). وتستعمل أيضًا صيغة قريبة هي a^p ≡ a (mod p).
أهمية المبرهنة تظهر عند التعامل مع أسس كبيرة. بدل حساب قوة ضخمة مباشرة، نستفيد من تكرار البواقي ضمن الحساب المعياري عندما يكون المعامل أوليًا.
مبرهنة فيرما الصغرى قاعدة في الحساب المعياري توضّح كيف تتكرر القوى عند القسمة على عدد أولي.
الحاسبة تدعم ثلاثة استخدامات فقط لمبرهنة فيرما
في وضع التحقق من المبرهنة، تقارن الحاسبة بين a^p mod p وa mod p. يجب أن يكون p عددًا أوليًا حتى ينطبق نطاق المبرهنة.
في وضع اختزال القوى، تحسب الحاسبة a^n mod p اعتمادًا على دورة فيرما. وفي وضع المعكوس المعياري، تحسب a^(-1) mod p بصيغة a^(p−2) mod p.
الحاسبة لا تولد مفاتيح RSA، ولا تنفذ تشفيرًا، ولا تقدم أي ادعاء أمني. وظيفتها تعليمية ومحدودة بالحالات الثلاث المذكورة في العقد.
يجب أن يكون المعامل p أوليًا
الصيغة القياسية لمبرهنة فيرما الصغرى تعمل مع معامل أولي. لذلك يمكن استعمالها مع p = 7 مثلًا، لكن لا يصح تعميم القاعدة نفسها تلقائيًا على p = 8 أو p = 9.
كذلك، صيغة a^(p−1) ≡ 1 (mod p) تحتاج أن يكون a وp متباينين نسبيًا. إذا كان a من مضاعفات p، فيجب تفسير النتيجة حسب شروط المبرهنة لا حسب قاعدة المعكوس.
يفحص runtime أن p أولي لحماية نطاق المبرهنة. هذا لا يجعل الصفحة أداة عامة لاختبار أولية الأعداد أو تنفيذ خوارزمية مثل Miller-Rabin.
اختزال القوى يعتمد على دورة p−1
عندما يكون p أوليًا ولا يكون a من مضاعفات p، تعطينا مبرهنة فيرما a^(p−1) ≡ 1 (mod p). لذلك يمكن اختزال الأس n حسب باقي قسمته على p−1.
مثال: لحساب 2^100 mod 7 نستخدم p−1 = 6. بما أن 100 يترك باقيًا 4 عند القسمة على 6، تصبح المسألة 2^4 mod 7.
هذه الصفحة لا تطبق مبرهنة أويلر للمعاملات غير الأولية، ولا تقدم نظرية عامة للأسس المعيارية. المحتوى ملتزم بالمعامل الأولي فقط.
المعكوس المعياري يحسب بصيغة a^(p−2)
المعكوس المعياري للعدد a بترديد p هو عدد x يحقق a × x ≡ 1 (mod p). إذا كان p أوليًا ولم يكن a من مضاعفات p، فإن فيرما الصغرى تعطي x ≡ a^(p−2) (mod p).
مثال: معكوس 3 بترديد 7 يحسب من 3^(7−2) = 3^5. بما أن 3^5 mod 7 = 5، فإن 5 هو المعكوس المعياري. التحقق: 3 × 5 = 15، و15 mod 7 = 1.
المقلوب العادي للعدد 3 هو 1/3. أما معكوسه المعياري بترديد 7 فهو 5، لأنه يعطي باقيًا يساوي 1 عند ضربه في 3.
الأمثلة تفصل بين التحقق واختزال القوى والمعكوس المعياري
مثال التحقق: عند a = 3 وp = 7 نحصل على 3^7 mod 7 = 3، فتتحقق صيغة a^p ≡ a (mod p).
مثال اختزال القوى: في 2^100 mod 7 لدينا 100 ≡ 4 (mod 6)، لذلك 2^100 ≡ 2^4 ≡ 16 ≡ 2 (mod 7).
مثال المعكوس المعياري: 3^5 mod 7 = 5، لذلك 5 هو معكوس 3 بترديد 7.
أسئلة شائعة
ما هي مبرهنة فيرما الصغرى؟
إذا كان p عددًا أوليًا وكان gcd(a,p)=1، فإن a^(p−1) ≡ 1 (mod p). وتوجد صيغة قريبة هي a^p ≡ a (mod p).
لماذا يجب أن يكون p عددًا أوليًا؟
لأن هذه الحاسبة تستخدم صيغة فيرما الخاصة بالمعامل الأولي. المعاملات غير الأولية تحتاج قواعد أخرى مثل مبرهنة أويلر.
ما هو المعكوس المعياري؟
هو عدد x يجعل حاصل الضرب a × x يترك باقيًا 1 عند القسمة على p.
هل المعكوس المعياري هو نفسه المقلوب؟
لا. المقلوب العادي هو 1/a، أما المعكوس المعياري فهو عدد صحيح داخل نظام mod يعطي باقيًا 1 عند الضرب.
هل تختبر هذه الحاسبة أولية أي عدد؟
لا. هي تتحقق من شرط p للحساب المدعوم، لكنها ليست أداة عامة لاختبار الأولية أو تنفيذ خوارزميات فحص متقدمة.
هل تصلح هذه الحاسبة للتشفير أو RSA؟
لا. لا تولد مفاتيح، ولا تشفر رسائل، ولا تقدم تحليلًا أمنيًا. استخدامها هنا تعليمي في الحساب المعياري.