Teoria liczb i arytmetyka modularna: karta pracy z odpowiedziami

Darmowa karta pracy do druku – Teoria liczb i arytmetyka modularna: 6 zadań od łatwych do poziomu egzaminu, z kluczem odpowiedzi. Wydrukuj ją lub zapisz jako PDF.

Nowa karta pracyĆwicz online z podpowiedziami

Dla nauczycieli: można bezpłatnie drukować, kopiować i używać na zajęciach. Każdy nowy arkusz ma nowe wartości i własny klucz odpowiedzi. Będziemy wdzięczni za link do ExamProblems na stronie kursu.

Imię: ____________________   Data: ____________

1.Łatwy
aqbr177=?·45+??=?·?+??=?·?+?

Użyj algorytmu Euklidesa, aby znaleźć gcd(177, 45).

a = 177b = 45
gcd(177, 45) =
2.Łatwy
aqbr882=?·738+??=?·?+??=?·?+?

Znajdź najmniejszą wspólną wielokrotność lcm(882, 738). Najpierw użyj algorytmu Euklidesa dla NWD.

a = 882b = 738
lcm(882, 738) =
3.Średni

Znajdź funkcję φ Eulera φ(1331), czyli liczbę liczb całkowitych od 1 do 1331 względnie pierwszych z 1331.

n = 1331 = 113
φ(1331) =
4.Średni

Znajdź element odwrotny do 35 modulo 37: liczbę x, dla której 0 < x < 37 oraz 35·x ≡ 1 (mod 37).

a = 35n = 37
35−1 mod 37 =
5.Trudny

Użyj wielokrotnego podnoszenia do kwadratu, aby znaleźć 5046 mod 77.

a = 50k = 46n = 77
5046 mod 77 =
6.Trudny
232c = me​ mod n?m = cd​ mod nm(n, e) = (589, 13)d

Zaszyfruj wiadomość m = 232 kluczem publicznym RSA (n, e) = (589, 13). Znajdź szyfrogram c.

n = 589e = 13m = 232
c =

Klucz odpowiedzi

  1. 1. gcd(177, 45) = 3
  2. 2. lcm(882, 738) = 36162
  3. 3. φ(1331) = 1210
  4. 4. 35−1 mod 37 = 18
  5. 5. 5046 mod 77 = 71
  6. 6. c = 275

Pełne rozwiązania krok po kroku: ćwicz ten temat na examproblems.com.