Zadanie 3.2. Szybkie potęgowanie modularne — informatyka 2022

Wprowadzenie

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 = a^x mod M,

gdzie a, M – dodatnie liczby całkowite, x – nieujemna liczba całkowita.

Mówimy wtedy, że a^x modulo M równa się b.

Przykład:

Dla a = 2, x = 5, M = 7 liczymy resztę z dzielenia 2⁵ (czyli 32) przez 7, zatem b = 4. Dla a = 3, x = 3 i M = 11 mamy b = 3³ mod 11 = 5, natomiast dla a = 10, x = 2 i M = 13 wynikiem jest b = 10² mod 13 = 9.

Informacja do zadań 3.3.−3.5.

W pliku liczby.txt jest 1 000 wierszy, w każdym − po trzy nieujemne liczby całkowite, kolejno M, a, b, oddzielone pojedynczymi spacjami. Liczby w pliku są nie większe niż 10 000, a ponadto wszystkie liczby M i a są większe bądź równe 2.

Napisz program(-y), który(-e) znajdzie(-dą) odpowiedzi do poniższych zadań. Każdą odpowiedź zapisz w pliku wyniki3.txt i poprzedź ją numerem odpowiedniego zadania. Do Twojej dyspozycji jest plik liczby_przyklad.txt, w którym zapisano 5 wierszy w formacie opisanym wyżej. Odpowiedzi dla pliku przykładowego są podane przy odpowiednich zadaniach − możesz ich użyć, aby sprawdzić poprawność działania swojego programu.

Polecenie

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 = a^x 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.

Specyfikacja:

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 a^x mod M.

Odpowiedź CKE

1) Rozwiązanie w pseudojęzyku, używające rekursji:

funkcja potęga(a, x, M) jeżeli x = 0 wynik 1 jeśli x mod 2 == 0: w = potęga(a, x/2) wynik w*w mod M jeśli x mod 2 == 1: w = potęga(a, (x-1)/2) zwróć wynik a*w*w mod M

2) Rozwiązanie w C++, metodą iteracyjną:

int potega(int a, int x, int M) { int w = 1; int z = a; while(x>0) { if (x%2==1) w = w*z%M; z = z*z%M; x = x/2; } return w; }

Zasady oceniania CKE

4 pkt – za poprawny algorytm, w tym:

3 pkt – za poprawne obliczenie potęgi a^x (w tym 1 punkt za warunki początkowe oraz 2 punkty za poprawną konstrukcję pętli z uwzględnieniem parzystości x)

1 pkt – za zwrócenie poprawnego wyniku.

2 pkt – za poprawny algorytm o złożoności większej niż logarytmiczna.

0 pkt – za podanie odpowiedzi niepoprawnej lub niepełnej albo brak odpowiedzi.

3.2. Szybkie potęgowanie modularne