AlgoVerse

توان پیمانه‌ای (مربع‌سازی پیاپی)

aᵇ mod n را با حدود log b ضرب حساب می‌کند: پایه را پشت سر هم مربع می‌کند و برای هر بیت ۱ توان، آن را در جواب ضرب می‌کند.

حساب کردن aᵇ با b − 1 ضرب برای b بزرگ (مثلاً در RSA) ناممکن است. ولی اگر b را در مبنای ۲ بنویسیم:

ادامه‌ی توضیح ↓
ورودی:
a=7 · b=560 · n=561خروجی PDF

۷⁵⁶⁰ mod ۵۶۱ = ۱؛ ۵۶۰ ده بیت دارد، پس به‌جای ۵۵۹ ضرب، ۱۳ ضرب (۱۰ مربع و ۳ ضرب در جواب) کافی است.

  1. def mod_pow(a, b, n):
  2. # a to the power b, mod n, reading the bits of b from the right.
  3. result = 1 % n
  4. base = a % n
  5. rows = []
  6. while b > 0:
  7. bit = b % 2
  8. if bit == 1:
  9. result = result * base % n
  10. rows.append((bit, base, result))
  11. base = base * base % n
  12. b = b // 2
  13. return result

ناوردا: result · baseᵇ mod n همیشه برابر جواب نهایی aᵇ mod n است (با b و base فعلی).

شروع اجرا

b560
base—
result—

جدول هنوز خالی است.

متغیرهای محلی

a7
b560
n561

نارنجی = در همین گام عوض شد

Call stack

  1. mod_pow()خط 1
گام ۱ از ۶۹
خط سیاه = square · خط نارنجی = گام کلیدیsquare: 0/10 · multiply: 0/3 · done: 0/1
    توضیح

    ایده

    حساب کردن aᵇ با b − 1 ضرب برای b بزرگ (مثلاً در RSA) ناممکن است. ولی اگر b را در مبنای ۲ بنویسیم:

    b = 560 = 1000110000₂   ⇒   a⁵⁶⁰ = a⁵¹² · a³² · a¹⁶

    توان‌های a¹, a², a⁴, a⁸, … با مربع کردن پیاپی به دست می‌آیند و فقط آن‌هایی که بیتشان ۱ است در جواب ضرب می‌شوند. بعد از هر ضرب mod n می‌گیریم تا عددها کوچک بمانند.

    هزینه

    حداکثر 2 log b ضرب. پایه‌ی RSA، آزمون میلر–رابین و دیفی–هلمن.

    در trace به چه چیزی نگاه کنی

    • هر سطر جدول یک بیت از b است (از راست): بیت، پایه‌ی آن دور و جواب تا آن لحظه.