Hızlı Üs Alma

Matematik / Sayı Teorisi O(log exp) O(1)

Tabanı karesini alarak ve yalnızca üssün 1-bitlerinde çarparak baseᵉˣᵖ mod m'yi O(log üs) sürede hesaplar.

13 = 1101₂

result = 1base = 3exp = 13

TabanÜsMod

1/18

3^13 mod 100 hesaplanıyor. result = 1 ile başlanıyor.

Değişmezresult · base^exp baştan sona cevaptır; her tur üssü yarıya indirir.

aktif bitişlenen bit

fast-exponentiation.c

long long power(long long b, long long e, long long m) {
    long long result = 1;
    b %= m;
    while (e > 0) {
        if (e & 1)                /* low bit set? */
            result = result * b % m;
        b = b * b % m;            /* square */
        e >>= 1;                  /* shift right */
    }
    return result;
}

Hızlı Üs Alma nasıl çalışır?

Tabanın karesini tekrar tekrar al (b, b², b⁴, …) ve yalnızca üssün ikilik basamağı 1 olan yerlerde sonuca çarp. 2⁶⁴ boyutlu üsler yalnızca 64 tur sürer.

Ne zaman kullanılır?

Kriptografide modüler kuvvetler, doğrusal yinelemeler için hızlı matris kuvveti, her yerde büyük üsler.