الأس المعياري – baseᵉ mod m

حساب baseᵉ mod m بتكوين baseᵉ أولاً ينفجر — فالعدد 2¹⁰⁰⁰ من 302 رقماً — لذا تربّع الطريقة وتختزل مقام m في كل خطوة مبقيةً الأعداد صغيرة. للعدد 2¹⁰ مقام 1000 والأس 10 = 1010₂: ابدأ بـ 2 ثم ربّع إلى 4 ثم ربّع إلى 16 واضرب فتصبح 32 ثم ربّع إلى 1024 ≡ 24. وتطبع الحاسبة التمدد الثنائي للأس وكل تربيع مع اختزاله وعمليات الضرب على البتات الواحدة. والعدد 3⁴ مقام 5 يربّع مرتين: 3² = 9 ≡ 4 ثم 4² = 16 ≡ 1 — الجواب 1. والكلفة O(log e) ضربة، ولهذا اختير أس RSA 65537 = 2¹⁶+1 متناثر البتات: 17 تربيعاً وضربة واحدة. وتظهر مفاهيم فيرما الصغرى: a^(p−1) ≡ 1 (mod p) لاختزال الأسوس مقام أولي.

1. 1

   أدخل الأساس والأس والقاسم

   مثل 2 و10 و1000

2. 2

   اكتب الأس ثنائياً

   الصيغة 1010 للعدد 10 توجه العمليات

3. 3

   ربّع واختزل

   كل خطوة تأخذ mod فوراً: 4 ثم 16 ثم 256

4. 4

   اضرب على البتات الواحدة

   التركيب حسب الخانات الثنائية يبلغ 24

• 1

  اختزل بعد كل ضرب — تبقى الأعداد تحت m²

• 2

  الكلفة تتناسب مع لوغاريتم الأس لا الأس نفسه

• 3

  لقاسم أولي m قلّص الأس مقام m−1 (فيرما)

• بناء القوة الكاملة قبل الاختزال — فيض

• تخطي اختزال بين تربيعات على مدخلات كبيرة

• نسيان الضربة الأخيرة للبت الأدنى

• تطبيق اختزال فيرما وقاسم m مركب