Processing math: 100%

Potęgowanie modularne

Potęgowanie modularne. Naszym celem jest policzenie

ab mod n.

Oczywiście, możemy założyć, że 0a<n, bo inaczej najpierw można policzyć resztę a z dzielenia a przez n, a dopiero potem (a)b mod n, jako że (a)b mod n=ab mod n. Zauważmy, że w przeciwieństwie do zwykłego potęgowania wynik nigdy nie przekracza n, czyli nie rośnie wykładniczo w stosunku do a. Pozwala to żywić nadzieję na szybsze algorytmy potęgujące. Dla rozgrzewki przeanalizujmy najpierw naiwny sposób liczenia potęgi modulo:

  • Naiwne potęgowanie modulo. Wymnóż a przez siebie b-krotnie, po każdym mnożeniu weź resztę modulo n. Branie reszty po każdym mnożeniu, utrzymuje tymczasowy iloczyn w zbiorze {0,,n1}. Zatem wykonywanych jest b mnożeń liczb O(logn)-bitowych, czyli wykonywanych jest O(blog2n) operacji bitowych. Jest to zatem algorytm działający w czasie wykładniczym względem rozmiaru wejścia O(logb+logn).
  • Szybkie potęgowanie modulo. Niech b=(bk1b0)2 będzie binarnym zapisem liczby b. Zauważmy, że ab mod n=k1i=0abi2i mod n.

Policzmy zatem w następujacy sposób kolejne potęgi a występujące w iloczynie:

aa mod nna2 mod n,(a2 mod n)(a2 mod n)na4 mod n,(a2k2 mod n)(a2k2 mod n)na2k1 mod n.

Tym sposobem wykonanych zostanie k2 mnożeń i dzieleń liczb O(logn)-bitowych, czyli O(klog2n) operacji bitowych. Aby otrzymać wynik musimy jeszcze wymnożyć przez siebie te potęgi, ktorym odpowiada bit 1 w liczbie b. Wykonanych zostanie więc jeszcze co najwyżej k mnożeń (które przeplatamy braniem reszty modulo n) liczb O(logn)-bitowych.

W sumie wykonanych zostanie O(klog2n)=O(logblog2n) operacji bitowych, a więc znacznie mniej niż sposobem naiwnym. Przedstawiony algorytm jest efektywny (wielomianowy względem długości wejścia).

Przykład

712 mod 10=?

  • 12=(1100)2,
  • wyznaczamy wybrane potęgi 7 modulo 10:
    • 72=49109,
    • 741099=81101,
    • 781011=1,
  • 712=78741011=1.
  • wykonane zostały tylko 4 mnożenia!

Przykład

351 mod 13=?

  • 51=(110011)2,
  • wyznaczamy wybrane potęgi 3 modulo 13:
    • 32=9,
    • 34=99=81133,
    • 381333=9,
    • 3161399=81133,
    • 3321333=9.
  • 351=3323163231139393=729131.