Darmowe konto pozwoli wrócić do niego później.
Polecenie
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 = 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:
Darmowe konto pozwoli wrócić do niego później.
Dla a = 2, x = 5, M = 7 liczymy resztę z dzielenia 2^5 (czyli 32) przez 7, zatem b = 4.
Dla a = 3, x = 3 i M = 11 mamy b = 3^3 mod 11 = 5,
natomiast dla a = 10, x = 2 i M = 13 wynikiem jest b = 10^2 mod 13 = 9.
Zadanie 3.1.
Uzupełnij tabelę – podaj brakującą liczbę (x lub b), dla której a^x mod M = b.
| M | a | x | b |
|---|---|---|---|
| --- | --- | --- | --- |
| 7 | 2 | 5 | 4 |
| 11 | 3 | 3 | |
| 31 | 5 | 25 | |
| 59 | 2 | 5 | |
| 80 | 9 | 2 |
Wiersz 2: b=5 (3^3 mod 11 = 27 mod 11 = 5)
Wiersz 3: x=2 (5^2 mod 31 = 25)
Wiersz 4: x=6 (2^6 mod 59 = 64 mod 59 = 5)
Wiersz 5: b=1 (9^2 mod 80 = 81 mod 80 = 1)
za poprawną odpowiedź. 1 pkt – za poprawnie wypełnione przynajmniej dwa pola tabeli.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.