Zadanie 3.3, 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
2 punktyInformacja 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.
Oblicz, w ilu wierszach pliku liczby.txt liczba M jest liczbą pierwszą.
Dla pliku liczby_przyklad.txt odpowiedź wynosi 2.
Do oceny oddajesz:
• plik tekstowy wyniki3.txt zawierający odpowiedzi do poszczególnych zadań (odpowiedź do każdego zadania powinna być poprzedzona jego numerem)
• pliki zawierające kody źródłowe Twoich programów o nazwach odpowiednio:
zadanie 3.3
zadanie 3.4
zadanie 3.5
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
343
Schemat punktowania
za poprawną odpowiedź.
za odpowiedź różniącą się od poprawnej o 1.
za podanie odpowiedzi niepoprawnej lub niepełnej albo brak odpowiedzi.