توان سریع (Fast Exponentiation)

توان سریع: محاسبه توان در O(log n) با مربع‌سازی متوالی و باقیمانده توان برای رمزنگاری

مسئله

محاسبه aⁿ یا aⁿ mod m. روش ساده: n−1 ضرب — O(n). برای n=10¹⁸ غیرممکن! توان سریع: O(log n).

ایده: مربع‌سازی

a¹⁰ = (a⁵)² و a⁵ = a × (a²)² — هر گام نصف!

pow(a, n):
    اگر n == 0: return 1
    نصف = pow(a, n // 2)
    اگر n زوج: return نصف × نصف
    وگرنه: return نصف × نصف × a

n در هر گام نصف ← log₂n گام!

نسخه تکراری با بیت‌ها

توان n را باینری بنویسید؛ هر بیت ۱ یعنی «مربع فعلی را در جواب ضرب کن»:

result = 1
while n > 0:
    if n & 1:            # بیت آخر ۱
        result *= base
    base *= base         # مربع
    n >>= 1              # بیت بعدی

مثال: 3¹³ = 3^(1101₂) = 3⁸ × 3⁴ × 3¹

باقیمانده توان (Modular Exponentiation)

در رمزنگاری، aⁿ mod m با n عظیم لازم است. کلید: بعد از هر ضرب mod بگیر — اعداد کوچک می‌مانند!

پایتون آماده دارد!

pow(a, n)          # توان
pow(a, n, m)       # توان با mod — دقیقاً همین الگوریتم!

اما برای مصاحبه، پیاده‌سازی لازم است — ۵ خط!

نکته: همین ایده «نصف‌کردن توان» پایه الگوریتم‌های زیادی است: توان ماتریسی (فیبوناچی در O(log n))، ضرب اعداد بزرگ، رمزنگاری Diffie-Hellman. یک الگو، هزار کاربرد!

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.

ابزارهای مرتبط