Zadanie 3.2, specimen 2023, informatyka rozszerzona

4 pktotwarteśrednie (szac.)Specimen 2023

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 punkty

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.

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.

Wypróbuj za darmo

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

4 pkt

za poprawny algorytm, w tym:

3 pkt

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),

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.

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.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.