Hızlı Kuvvet Alma: Bir Milyar Çarpmadan Otuza İnmek

Naif yöntem niye yetersiz?

$a^n$ hesaplamak için aklınıza ilk gelen ne olur? "n−1 defa $a$ ile çarp." Yani:

$a^5 = a \cdot a \cdot a \cdot a \cdot a$

Dört çarpma. $a^{100}$ için 99 çarpma. $a^{1\,000\,000\,000}$ için bir milyar çarpma. Bilgisayar saniyede milyarlarca işlem yapsa bile bu sayıların çok büyük olduğu (yüzlerce basamaklı) bir bağlamda — örneğin RSA şifrelemesinde — naif yöntem dakikalar sürer. Oysa kareleme tabanlı yöntem aynı işi milisaniyenin altında bitirir.

Kareleme ile kuvvet alma

Hile basit: önce $a^2$ hesapla, sonra $(a^2)^2 = a^4$, sonra $(a^4)^2 = a^8$… Her kareleme üssü ikiye katlar. $a^{16}$'yı yalnızca dört kareleme ile elde edersin:

$a \to a^2 \to a^4 \to a^8 \to a^{16}$

Peki $a^{13}$ gibi 2'nin kuvveti olmayan sayılar? Üssü ikili tabanda yaz:

$13 = 8 + 4 + 1 = (1101)_2$

O zaman $a^{13} = a^8 \cdot a^4 \cdot a^1$. Yani önce karelemeyle $a, a^2, a^4, a^8$'i hazırla; sonra ikili gösterimde 1 olan basamaklara karşılık gelenleri çarp. Toplam çarpma sayısı $\lceil \log_2 n \rceil$ kareleme + en fazla $\lceil \log_2 n \rceil$ ek çarpma.

"Bir milyar çarpma"dan otuza

$n = 10^9$ için $\log_2 10^9 \approx 30$. Yani naif yöntemin gerektirdiği bir milyar çarpma yerine yaklaşık 60 çarpma (30 kareleme + en fazla 30 ek). 30 milyon kat hızlanma. Üstelik küçük üsler için fark dramatik değilken üs ne kadar büyürse algoritma o kadar fark atar.

Pseudo-kod (sade)

function pow(a, n):
    result = 1
    base = a
    while n > 0:
        if n is odd:
            result = result * base
        base = base * base
        n = n // 2
    return result

Her döngüde $n$ ikiye bölünür; en sondaki bit 1 ise sonuca mevcut $base$ eklenir. Klasik "square-and-multiply" örüntüsü.

Tarihte iz: Pingala'dan İbni Sina'ya

Bu fikir aslında çok eskidir. Pingala adlı Hint matematikçi (M.Ö. 2. yüzyıl) Sanskrit prosodisi (vezin) üzerine yazdığı eserde 2'nin kuvvetlerini ikili gösterimle bağdaştırmıştı. Orta Çağ İslam matematikçileri (örn. Al-Karaji, İbn Yahya el-Maghribi al-Samaw'al) cebirsel kuvvetlerin hesaplanmasında benzer kısa yolları kullandı. Avrupa'da algoritmanın modern hali 17. yüzyılda Briggs'in logaritma tablolarında belirgin hale geldi.

RSA: niye bu algoritma olmadan modern internet çalışmaz?

Modern şifreleme (RSA, Diffie-Hellman, ElGamal) modüler üs almaya dayanır:

$c \equiv m^e \pmod n$

Burada $e$ ve $n$ tipik olarak 2048 bit (yaklaşık 600 basamak) uzunluğunda sayılardır. Naif yöntem $2^{2048}$ kadar çarpma ister — evrenin ömründen uzun. Kareleme yöntemiyle yalnızca ~2048 modüler çarpma yapılır; modern CPU bunu milisaniyede bitirir.

Her HTTPS bağlantısı kurarken, banka uygulamasına girerken, mesajlaşma uygulamasında "bitmiş güvenlik" simgesini görürken arka planda bu algoritma çalışıyor. Hız olmadan kriptografi olmazdı; algoritma olmadan hız olmazdı.

Genel ders: "doğal yöntem" çoğu zaman en kötüsüdür

Çarpma için tekrarlı toplama, kuvvet için tekrarlı çarpma, arama için tek tek bakma — hepsi sezgisel ama hepsi $O(n)$. Akıllı bir bölme/birleştirme stratejisi (böl ve fethet, kareleme, ikili arama) çoğu zaman bunları $O(\log n)$'a indirir. Logaritmik fark, ölçek büyüdükçe gözünüze inanılmaz görünür.

Bir milyar yerine otuz. Aradaki köprü: ikili gösterim. Aynı ikili gösterim ki bilgisayarın ne dediğini bildiği tek dildir.