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

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.

Остатки можно приводить на каждом шаге, что сохраняет числа небольшими:

Например, 47·58 mod 9: 47 ≡ 2 и 58 ≡ 4, поэтому 47·58 ≡ 8 (mod 9).

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

Наибольший общий делитель НОД(a, b) — это наибольшее число, которое делит оба. Алгоритм Евклида использует НОД(a, b) = НОД(b, a mod b):

1. Разделите: a = q·b + r.
2. Замените (a, b) на (b, r).
3. Повторяйте, пока остаток не станет равен 0. Последний ненулевой остаток и есть НОД.

Из него следует наименьшее общее кратное: НОК(a, b) = a·b / НОД(a, b).

3Обратные элементы и расширенный алгоритм

Обратный к a по модулю n — это число x, для которого a·x ≡ 1 (mod n). Он существует тогда и только тогда, когда НОД(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 = НОД(a, n) больше 1, то при d, делящем b, решений d, а иначе решений нет.

Два сравнения со взаимно простыми модулями, x ≡ r₁ (mod m₁) и x ≡ r₂ (mod m₂), имеют ровно одно решение по модулю m₁·m₂ (китайская теорема об остатках). Запишите x = r₁ + m₁k и решите относительно k.

4Степени по модулю и RSA

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

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

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

1. n = p·q и φ(n) = (p − 1)(q − 1).
2. Выберите e с НОД(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ᵏ − pᵏ⁻¹, и φ мультипликативна для взаимно простых множителей.

5Типичные ошибки

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

6Как выглядят экзаменационные задачи

• Лёгкий: НОД и остатки. Вы применяете алгоритм Евклида для НОД или НОК, находите остатки отрицательных чисел и приводите суммы и произведения по модулю n.
• Средний: обратные элементы и сравнения. Вы находите обратные по модулю с помощью расширенного алгоритма, решаете линейные сравнения, объединяете два сравнения по китайской теореме об остатках и вычисляете функцию Эйлера φ(n).
• Сложный: степени по модулю и RSA. Вы используете многократное возведение в квадрат и теорему Ферма, решаете сравнения с несколькими решениями, находите закрытые показатели RSA, шифртексты и расшифрованные сообщения.