Теория чисел и модульная арифметика: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Теория чисел и модульная арифметика»: 6 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

Для преподавателей: можно бесплатно печатать, копировать и использовать на занятиях. Каждый новый лист содержит новые значения и собственные ответы. Будем благодарны за ссылку на ExamProblems на странице вашего курса.

Имя: ____________________   Дата: ____________

1.Лёгкая
aqbr754=?·91+??=?·?+??=?·?+?

Используйте алгоритм Евклида, чтобы найти gcd(754, 91).

a = 754b = 91
gcd(754, 91) =
2.Лёгкая
aqbr50=?·17+??=?·?+??=?·?+?

Найдите наименьшее общее кратное lcm(50, 17). Сначала найдите НОД по алгоритму Евклида.

a = 50b = 17
lcm(50, 17) =
3.Средняя

Найдите обратный к 23 по модулю 71: число x, для которого 0 < x < 71 и 23·x ≡ 1 (mod 71).

a = 23n = 71
23−1 mod 71 =
4.Средняя

Найдите обратный к 8 по модулю 13: число x, для которого 0 < x < 13 и 8·x ≡ 1 (mod 13).

a = 8n = 13
8−1 mod 13 =
5.Сложная

47 — простое число. Используйте малую теорему Ферма, чтобы найти 233318 mod 47.

p = 47k = 33318
233318 mod 47 =
6.Сложная
277c = me​ mod n?m = cd​ mod nm(n, e) = (611, 13)d

Зашифруйте сообщение m = 277 открытым ключом RSA (n, e) = (611, 13). Найдите шифртекст c.

n = 611e = 13m = 277
c =

Ответы

  1. 1. gcd(754, 91) = 13
  2. 2. lcm(50, 17) = 850
  3. 3. 23−1 mod 71 = 34
  4. 4. 8−1 mod 13 = 5
  5. 5. 233318 mod 47 = 28
  6. 6. c = 4

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.