Теорія чисел і арифметика за модулем: задачі з покроковими розв’язками

Безкоштовні задачі з теми Теорія чисел і арифметика за модулем з рисунками, підказками й повними розв’язками. Щоразу нові значення, трьох рівнів: НСД і залишки, обернені елементи та конгруенції, степені за модулем і RSA.

Безкоштовна задачаЛегка
012345678910mod 11

Знайдіть 942 mod 11, залишок r, де 0 ≤ r < 11.

a = 942n = 11

Точна відповідь: ціле число, без округлення.

Наступна задача →
Тренуйтеся безкоштовно: Теорія чисел і арифметика за модулемТренуйтеся зараз: Теорія чисел і арифметика за модулемБезкоштовних задач щодня: 5. Без картки.

Що ви тренуєте

  1. ЛегкаНСД і залишки
  2. Середняобернені елементи та конгруенції
  3. Складнастепені за модулем і RSA

Як розв’язувати задачі на тему «Теорія чисел і арифметика за модулем»

  1. Спершу зведіть кожне число за модулем n; залишки лежать між 0 і n − 1.
  2. Для НСД діліть послідовно за алгоритмом Евкліда; останній ненульовий залишок і є НСД.
  3. Для оберненого елемента виконайте розширений алгоритм і візьміть коефіцієнт при a; якщо він від’ємний, додайте n.
  4. Розв’язуйте a·x ≡ b множенням на a⁻¹; поєднуйте дві конгруенції, записавши x = r₁ + m₁k.
  5. Для степенів запишіть показник у двійковому вигляді й послідовно підносьте до квадрата; в RSA d = e⁻¹ mod φ(n), де φ(n) = (p − 1)(q − 1).

Типові помилки

  • Давати від’ємний залишок для від’ємного числа.
  • Зупинити алгоритм Евкліда на першому залишку.
  • Залишити обернений елемент від’ємним замість додати n.
  • Брати показник RSA d за модулем n замість φ(n).
  • Зводити показник за модулем p замість p − 1 у теоремі Ферма.

Основні формули

Ділення із залишком
a = q·n + r, 0 ≤ r < n
Евклід
gcd(a, b) = gcd(b, a mod b)
Найменше спільне кратне
lcm(a, b) = a·b/gcd(a, b)
Обернена
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Лінійна конгруенція
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Функція Ейлера
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Ферма
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Вивчайте тему «Теорія чисел і арифметика за модулем» з нуля

1Залишки та конгруенції

Ділення a на n дає частку q і залишок r: a = q·n + r, де 0 ≤ r < n. Залишок записують a mod n. Для від’ємного числа q теж від’ємна: −3 = −1·7 + 4, тож −3 mod 7 = 4.

Два числа конгруентні за модулем n, a ≡ b (mod n), коли вони дають однаковий залишок, тобто коли n ділить a − b.

0123456mod 7−3 ≡ 411 ≡ 4

Залишки можна зводити на кожному кроці, що зберігає числа малими:

(a + b) mod n = ((a mod n) + (b mod n)) mod n, і так само для a·b

Наприклад, 47·58 mod 9: 47 ≡ 2 і 58 ≡ 4, тож 47·58 ≡ 8 (mod 9).

Самоперевірка Чому дорівнює −17 mod 5?
  1. 2
  2. 3
  3. −2
  4. −3

Відповідь: 3. −17 = −4·5 + 3, тож залишок дорівнює 3. Відповідь 2 — це 17 mod 5; залишок ніколи не буває від’ємним.

2Алгоритм Евкліда

Найбільший спільний дільник gcd(a, b) — це найбільше число, яке ділить обидва. Алгоритм Евкліда використовує gcd(a, b) = gcd(b, a mod b):

  1. Поділіть: a = q·b + r.
  2. Замініть (a, b) на (b, r).
  3. Повторюйте, доки залишок не стане 0. Останній ненульовий залишок і є НСД.
252 = 2·105 + 42, 105 = 2·42 + 21, 42 = 2·21 + 0 → gcd = 21

З нього випливає найменше спільне кратне: lcm(a, b) = a·b / gcd(a, b).

Самоперевірка Чому дорівнює gcd(84, 36)?
  1. 12
  2. 252
  3. 4
  4. 6

Відповідь: 12. 84 = 2·36 + 12 і 36 = 3·12 + 0, тож НСД дорівнює 12. Число 252 — це найменше спільне кратне, 84·36/12.

3Обернені елементи й розширений алгоритм

Обернений до a за модулем n — це число x, для якого a·x ≡ 1 (mod n). Він існує тоді й лише тоді, коли gcd(a, n) = 1.

Розширений алгоритм Евкліда виконує Евкліда на (n, a) і для кожного залишку веде коефіцієнт t, так що кожен залишок r ≡ t·a (mod n). Почніть із t = 0 для n і t = 1 для a; кожне нове t дорівнює t на два рядки вище мінус q, помножене на t на один рядок вище. Коли з’являється залишок 1, його t і є оберненим елементом.

З оберненим елементом конгруенція a·x ≡ b (mod n) розв’язується як x ≡ a⁻¹·b. Коли d = gcd(a, n) більше за 1, існує d розв’язків, якщо d ділить b, і жодного інакше.

Дві конгруенції з взаємно простими модулями, x ≡ r₁ (mod m₁) і x ≡ r₂ (mod m₂), мають рівно один розв’язок за модулем m₁·m₂ (китайська теорема про лишки). Запишіть x = r₁ + m₁k і розв’яжіть відносно k.

Розв’язаний приклад

Знайдіть обернений до 7 за модулем 40.

1

Евклід на (40, 7)

40 = 5·7 + 5, 7 = 1·5 + 2, 5 = 2·2 + 1
2

Ведіть коефіцієнт t

t(40) = 0, t(7) = 1.

t(5) = 0 − 5·1 = −5, t(2) = 1 − 1·(−5) = 6, t(1) = −5 − 2·6 = −17
3

Зробіть його додатним

1 ≡ −17·7 (mod 40), а −17 + 40 = 23.

4

Перевірка

7·23 = 161 = 4·40 + 1
Відповідь

Обернений елемент — 7⁻¹ ≡ 23 (mod 40).

4Степені за модулем і RSA

Повторне піднесення до квадрата швидко обчислює aᵏ mod n: запишіть k у двійковому вигляді, знайдіть a, a², a⁴, a⁸, … mod n піднесенням до квадрата й зведенням, а тоді перемножте степені, біти яких дорівнюють 1.

Мала теорема Ферма: для простого p, що не ділить a, aᵖ⁻¹ ≡ 1 (mod p). Тож показник можна зводити за модулем p − 1.

RSA будує ключ із двох простих чисел p і q:

  1. n = p·q і φ(n) = (p − 1)(q − 1).
  2. Оберіть e з gcd(e, φ(n)) = 1; (n, e) — відкритий ключ.
  3. Обчисліть d = e⁻¹ mod φ(n): це закритий ключ.
  4. Шифруйте c = mᵉ mod n; дешифруйте m = cᵈ mod n.

Функція Ейлера φ(n) рахує числа від 1 до n, взаємно прості з n: φ(p) = p − 1 для простого, φ(pᵏ) = pᵏ − pᵏ⁻¹, а φ мультиплікативна для взаємно простих множників.

Самоперевірка Ключ RSA використовує p = 5, q = 11 і e = 3. Чому дорівнює d?
  1. 13
  2. 27
  3. 37
  4. 3

Відповідь: 27. φ(n) = 4·10 = 40, а 3·27 = 81 = 2·40 + 1, тож d = 27. Обернений до 3 за модулем n = 55 був би 37, але d беруть за модулем φ(n).

5Типові помилки

  • Давати від’ємний залишок для від’ємного числа: −17 mod 5 дорівнює 3, а не −2.
  • Зупиняти Евкліда на першому залишку замість останнього ненульового.
  • Забувати додати n до від’ємного коефіцієнта з розширеного алгоритму.
  • Обчислювати показник RSA d за модулем n замість за модулем φ(n).
  • Зводити показник за модулем p замість p − 1 у теоремі Ферма.

6Як виглядають екзаменаційні запитання

  • Легкий: НСД і залишки. Ви виконуєте алгоритм Евкліда для НСД чи НСК, знаходите залишки від’ємних чисел і зводите суми та добутки за модулем n.
  • Середній: обернені елементи та конгруенції. Ви знаходите обернені за модулем розширеним алгоритмом, розв’язуєте лінійні конгруенції, поєднуєте дві конгруенції китайською теоремою про лишки та обчислюєте φ(n) Ейлера.
  • Складний: степені за модулем і RSA. Ви користуєтеся повторним піднесенням до квадрата й теоремою Ферма, розв’язуєте конгруенції з кількома розв’язками та знаходите закриті показники RSA, шифротексти й розшифровані повідомлення.

Вивчайте крок за кроком у застосункуВивчайте крок за кроком у застосунку

Розв’язані приклади

Приклад 1Легка

Знайдіть (914·953) mod 11, не перемножуючи великих чисел: спершу зведіть.

n = 11

Знайти: (914·953) mod 11

Показати підказки
  1. (x·y) mod n = ((x mod n)·(y mod n)) mod n, і те саме для сум.
  2. 914 mod 11 = 1, 953 mod 11 = 7.
  3. Зведіть добуток залишків за модулем 11.
Показати відповідь і покроковий розв’язок

Подільність і залишки: a mod n — це залишок r, де 0 ≤ r < n і a = q·n + r, також коли a від’ємне. Алгоритм Евкліда знаходить gcd(a, b) повторенням a = q·b + r і заміною (a, b) на (b, r); останній ненульовий залишок і є НСД. Тоді lcm(a, b) = a·b/gcd(a, b). Залишки можна зводити на кожному кроці: (a + b) mod n і (a·b) mod n залежать лише від a mod n і b mod n.

Зведіть кожне число

914 ≡ 1, 953 ≡ 7 (mod 11)

Об’єднайте

1·7 = 7 ≡ 7 (mod 11)

Відповідь

(914·953) mod 11 = 7
Приклад 2Середня

Знайдіть функцію Ейлера φ(637), кількість цілих чисел від 1 до 637, взаємно простих з 637.

n = 637 = 72·13

Знайти: φ(637)

Показати підказки
  1. Розкладіть n на прості множники: 637 = 72·13.
  2. φ мультиплікативна для взаємно простих множників, а φ(pᵏ) = pᵏ − pᵏ⁻¹.
  3. φ(n) = n·∏(1 − 1/p).
Показати відповідь і покроковий розв’язок

Обернені елементи та конгруенції: a має обернений за модулем n саме тоді, коли gcd(a, n) = 1. Розширений алгоритм Евкліда записує 1 = s·n + t·a, і тоді a⁻¹ ≡ t (mod n). Конгруенція a·x ≡ b (mod n) з gcd(a, n) = 1 має розв’язок x ≡ a⁻¹·b. Дві конгруенції x ≡ r₁ (mod m₁) і x ≡ r₂ (mod m₂) зі взаємно простими модулями мають один розв’язок за модулем m₁·m₂ (китайська теорема про лишки). Функція Ейлера φ(n) рахує числа від 1 до n, взаємно прості з n: φ(n) = n·∏(1 − 1/p).

Прості множники

637 = 72·13

Функція Ейлера

φ(637) = φ(49)·φ(13) = 42·12 = 504

Відповідь

φ(637) = 504
Приклад 3Складна
mc = me​ mod n225m = cd​ mod n?(n, e) = (481, 23)d

Ключ RSA використовує p = 13, q = 37 і e = 23. Розшифруйте шифротекст c = 225: знайдіть повідомлення m.

p = 13q = 37e = 23c = 225

Знайти: m

Показати підказки
  1. n = 481, φ(n) = 432.
  2. d = e⁻¹ mod φ(n) = 263.
  3. m = cd mod n = 225263 mod 481: використайте повторне піднесення до квадрата.
Показати відповідь і покроковий розв’язок

Степені за модулем і RSA: обчислюйте aᵏ mod n повторним піднесенням до квадрата: запишіть k у двійковому вигляді, підносьте до квадрата, зводьте після кожного кроку й перемножте степені, біти яких дорівнюють 1. Ферма: aᵖ⁻¹ ≡ 1 (mod p) для простого p, що не ділить a, тож показник можна зводити за модулем p − 1. RSA: оберіть прості p і q, n = p·q і φ(n) = (p − 1)(q − 1); відкритий показник e взаємно простий із φ(n), а закритий показник — d = e⁻¹ mod φ(n). Шифруйте за c = mᵉ mod n, а дешифруйте за m = cᵈ mod n.

Закритий показник

n = 481, φ(n) = 432
d = 23−1 mod 432 = 263

Розшифруйте повторним піднесенням до квадрата

263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)

Повідомлення

m = 361
перевірка: 36123 mod 481 = 225

Відповідь

m = 361

Запитання й відповіді

Теорія чисел і арифметика за модулем: що це?

Ділення a на n дає частку q і залишок r: a = q·n + r, де 0 ≤ r < n. Залишок записують a mod n. Для від’ємного числа q теж від’ємна: −3 = −1·7 + 4, тож −3 mod 7 = 4.

Два числа конгруентні за модулем n, a ≡ b (mod n), коли вони дають однаковий залишок, тобто коли n ділить a − b.

Теорія чисел і арифметика за модулем: як розв’язувати задачі крок за кроком?
  1. Спершу зведіть кожне число за модулем n; залишки лежать між 0 і n − 1.
  2. Для НСД діліть послідовно за алгоритмом Евкліда; останній ненульовий залишок і є НСД.
  3. Для оберненого елемента виконайте розширений алгоритм і візьміть коефіцієнт при a; якщо він від’ємний, додайте n.
  4. Розв’язуйте a·x ≡ b множенням на a⁻¹; поєднуйте дві конгруенції, записавши x = r₁ + m₁k.
  5. Для степенів запишіть показник у двійковому вигляді й послідовно підносьте до квадрата; в RSA d = e⁻¹ mod φ(n), де φ(n) = (p − 1)(q − 1).
Теорія чисел і арифметика за модулем: які помилки найпоширеніші?
  • Давати від’ємний залишок для від’ємного числа.
  • Зупинити алгоритм Евкліда на першому залишку.
  • Залишити обернений елемент від’ємним замість додати n.
  • Брати показник RSA d за модулем n замість φ(n).
  • Зводити показник за модулем p замість p − 1 у теоремі Ферма.
Теорія чисел і арифметика за модулем: що ви тренуєте?
  • Легка: НСД і залишки
  • Середня: обернені елементи та конгруенції
  • Складна: степені за модулем і RSA

Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь. Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.

Як проходить тренування

  • Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь.
  • Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.
  • Ваш прогрес, помилки та збережені задачі зберігаються, тож перед іспитом ви зможете все повторити.

Курси з цією темою

Основи інформатикиДискретна математика

Інші теми: Математика і статистика

ГраниціПохідніОптимізаціяІнтегралиПослідовності та рядиДиференціальне числення функцій багатьох зміннихДиференціальні рівнянняКомплексні числаЧисельні методиМатриці та визначникиВектори: скалярний і векторний добуткиЛогіка висловлювань і доведенняМножини, відношення та функціїТеорія графівІмовірністьОписова статистикаНормальний розподілДовірчі інтервалиПеревірка гіпотез і довірчі інтервалиЛінійна регресія та кореляціяКритерії хі-квадрат

Робочий аркуш для друку

Робочий аркуш «Теорія чисел і арифметика за модулем» з відповідями
Тренуйтеся безкоштовно: Теорія чисел і арифметика за модулемТренуйтеся зараз: Теорія чисел і арифметика за модулемБезкоштовних задач щодня: 5. Без картки.