Rozważmy operację potęgowania modularnego stosowaną np. w algorytmie RSA.
Liczbę a podnosimy do potęgi x, po czym bierzemy resztę z dzielenia otrzymanej liczby przez ustaloną liczbę M, dzięki czemu otrzymujemy wynik b = ax mod M, gdzie a, M – dodatnie liczby całkowite, x – nieujemna liczba całkowita.
Mówimy wtedy, że ax modulo M równa się b. Przykład: Dla a = 2, x = 5, M = 7 liczymy resztę z dzielenia 25 (czyli 32) przez 7, zatem b = 4. Dla a = 3, x = 3 i M = 11 mamy b = 33 mod 11 = 5, natomiast dla a = 10, x = 2 i M = 13 wynikiem jest b = 102 mod 13 = 9.
Zapisz w wybranej przez siebie notacji (w postaci pseudokodu lub w wybranym języku programowania) algorytm, który gdy są dane liczby a, x i M, obliczy b = ax mod M.
Aby otrzymać maksymalną liczbę punktów, Twój algorytm powinien wykonywać O(log x) operacji arytmetycznych wymienionych w poniższej uwadze.
Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, resztę z dzielenia, oraz porównywanie liczb; instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje.
Dane: a − liczba całkowita dodatnia x − nieujemna liczba całkowita M − liczba całkowita dodatnia
Wynik: b − nieujemna liczba całkowita o wartości równej ax mod M
brenna.txt kody.txt liczby.txt przybycia.txt statki.txt szachy.txt
Liczbę a podnosimy do potęgi x, po czym bierzemy resztę z dzielenia otrzymanej liczby przez ustaloną liczbę M, dzięki czemu otrzymujemy wynik b = ax mod M, gdzie a, M – dodatnie liczby całkowite, x – nieujemna liczba całkowita.
Mówimy wtedy, że ax modulo M równa się b. Przykład: Dla a = 2, x = 5, M = 7 liczymy resztę z dzielenia 25 (czyli 32) przez 7, zatem b = 4. Dla a = 3, x = 3 i M = 11 mamy b = 33 mod 11 = 5, natomiast dla a = 10, x = 2 i M = 13 wynikiem jest b = 102 mod 13 = 9.
Zapisz w wybranej przez siebie notacji (w postaci pseudokodu lub w wybranym języku programowania) algorytm, który gdy są dane liczby a, x i M, obliczy b = ax mod M.
Aby otrzymać maksymalną liczbę punktów, Twój algorytm powinien wykonywać O(log x) operacji arytmetycznych wymienionych w poniższej uwadze.
Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, resztę z dzielenia, oraz porównywanie liczb; instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje.
Dane: a − liczba całkowita dodatnia x − nieujemna liczba całkowita M − liczba całkowita dodatnia
Wynik: b − nieujemna liczba całkowita o wartości równej ax mod M