Strona główna » Algorytmy » Artykuły » Szybkie Potęgowanie Modulo
≡
 

Szybkie Potęgowanie Modulo

https://mattomatti.com/a0037

Wstęp

Szybkie Potęgowanie Modulo dotyczy równań takich jak xn ≡m z. Podczas operacji potęgowania mogą pojawić się dwa problemy: jeden związany z przepełnieniem zmiennej, a drugi z szybkością działania dla bardzo dużych wartości x i y. Korzystając z własności modulo oraz twierdzenia Eulera proces obliczania można znacząco przyśpieszyć.

Algorytm

Założenia

Przypuśćmy, że do wyliczenia jest wartość z w równaniu xn ≡m z. Wartości x, y i m są dane.

Rozpatrzmy na początek problem przepełnienia. Można go bardzo łatwo ominąć korzystając z faktu, że x mod m = (a mod m)(b mod m), gdzie x = ab. Oznacza to, że można rozpisać podane równanie jako: z = (((x·x mod m)·x mod m) ... )·x mod m. Dzięki takiemu zabiegowi wyjście poza zakres będzie możliwe jedynie wtedy, gdy x2 jest większe, równe maksymalnemu zakresowi typu zmiennej x.

Pozostaje teraz pytanie czy proces można przyśpieszyć. Otóż można wykorzystując w tym celu twierdzenie Eulera. Twierdzenia stwierdza, że dla dla dowolnych x i m jeśli NWD(m, x) = 1 to xϕ(m) ≡m 1, gdzie ϕ(m) to liczba wszystkich liczb względnie pierwszych z m. O sposobie wyliczania tej funkcji można przeczytać tutaj. Metoda ta w większości przypadków pozwoli znacznie ograniczyć liczbę potrzebnych operacji.

Implementacja

Prosta

Najprostsza implementacja szybkiego Potęgowania Modulo, która ma uniknąć problemów z przepełnieniem zmiennej ma następującą postać:

  1. int szybkiePotegowanieModulo(int x, int y, int m) {
  2.   int w = x;
  3.   for (int i = 1; i < y; i++)
  4.     w = (w * x) % m;
  5.   return w;
  6. }

Jednak nie jest to kod optymalny. Dalej został przedstawiony kod, który

Optymalizacja

Poniżej została przedstawiona przykładowa implementacja funkcji szybkiePotegowanieModulo(), która wylicza wynik xn mod m:

  1. int szybkiePotegowanieModulo(int x, int y, int m) {
  2.   int w = x;
  3.   if (nwd(x, m) == 1)
  4.     y = y % phi(m);
  5.   for (int i = 1; i < y; i++)
  6.     w = (w * x) % m;
  7.   return w;
  8. }

Algorytm jest bardzo krótki. (2.) Początkowo wartość wynikowa to x. Jeśli (3.) liczba potęgowana i dzielnik są względnie pierwsze to (4.) z potęgi jest odejmowana odpowiednia wartość. (5.) Następnie dla pozostałych potęg: (6.) aktualny wynik należy pomnożyć przez x i wyciągnąć resztę modulo m. Na koniec (7.) zwróć wartość w.

Czy względnie pierwsze?

Do sprawdzenia czy dwie wartości są względnie pierwsze wykorzystany został algorytm Euklidesa:

  1. int nwd(int a, int b) {
  2.   int c;
  3.   while (b != 0) {
  4.     c = a % b;
  5.     a = b;
  6.     b = c;
  7.   }
  8.   return a;
  9. }

Funkcja ϕ

Do wyliczania wartości funkcji ϕ użyty został następujący kod:

  1. int phi(int n) {
  2.   double suma = n;
  3.   int dzielnik = 2;
  4.   while (n != 1) {
  5.     while (n % dzielnik != 0)
  6.       dzielnik++;
  7.     suma *= (1 - 1.0 / dzielnik);
  8.     while (n % dzielnik == 0) {
  9.       n /= dzielnik;
  10.     }
  11.   }
  12.   return int(suma);
  13. }

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższej funkcji main():

  1. int main() {
  2.   int x, y, m;
  3.   cout << "Podaj liczbe potegowana x = ";
  4.   cin >> x;
  5.   cout << "Podaj potege liczby x, y = ";
  6.   cin >> y;
  7.   cout << "Podaj dzielnik m = ";
  8.   cin >> m;
  9.   cout << x << "^" << y << " mod m = ";
  10.   cout << szybkiePotegowanieModulo(x, y, m) << endl;
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Otrzymany wynik potęgowanie modulo nie jest jednoznaczny. Przykładowo 6 mod 5 = 1, ale poprawną odpowiedzią jest też np. 6 mod 5 = -4. Korzystając z tej wskazówki postaraj się tak zmienić wartość zmiennej x, aby jej wartość była jak najmniejsza podczas operacji potęgowania.