Zadanie 3.2, specimen 2023, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 3. Potęgowanie modulo
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.
Polecenie
4 punktyZapisz 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.
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 ax mod M
Algorytm:
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
Rozwiązanie 1 (rekursja):
```text
funkcja potęga(a, x, M)
jeżeli x = 0
wynik 1 mod M
jeśli x mod 2 == 0:
w = potęga(a, x/2, M)
wynik w*w mod M
jeśli x mod 2 == 1:
w = potęga(a, (x-1)/2, M)
zwróć wynik a*w*w mod M
```
Rozwiązanie 2 (C++, iteracja):
```cpp
int potega(int a, int x, int M) {
int w = 1 % M;
int z = a;
while(x>0) {
if (x%2==1)
w = w*z%M;
z = z*z%M;
x = x/2;
}
return w;
}
```
Schemat punktowania
za poprawny algorytm, w tym:
za poprawne obliczenie potęgi ax (w tym 1 punkt za warunki początkowe oraz 2 punkty za poprawną konstrukcję pętli z uwzględnieniem parzystości x),
za zwrócenie poprawnego wyniku.
za poprawny algorytm o złożoności większej niż logarytmiczna.
za podanie odpowiedzi niepoprawnej lub niepełnej albo brak odpowiedzi.
Komentarz. Algorytm winien wykorzystywać metodę binarną (szybkie potęgowanie) do osiągnięcia złożoności O(log x). Proste mnożenie iteracyjne daje tylko 2 punkty.