Вычеты и первообразные корни
Если отождествить все числа с одинаковым остатком, получится конечная алгебраическая система — кольцо вычетов ℤₘ. Его обратимые элементы образуют группу, в которой живут шифр Эль-Гамаля и протокол Диффи–Хеллмана, а первообразные корни и дискретный логарифм — основа их стойкости.
Классы вычетов и кольцо ℤₘ
Класс вычетов числа a по модулю m — множество [a] = {a + km : k ∈ ℤ} всех чисел, сравнимых с a. Любой элемент класса называется вычетом.
- Полная система вычетов — по одному представителю из каждого из m классов, например 0, 1, …, m − 1.
- Приведённая система вычетов — представители классов, взаимно простых с m.
Классы складываются и перемножаются через представителей: [a] + [b] = [a + b], [a]·[b] = [ab] — результат не зависит от выбора представителей (это и есть свойства сравнений). Получается коммутативное кольцо ℤₘ из m элементов.
Обратимые элементы и делители нуля
Ненулевой класс [a] ∈ ℤₘ обратим тогда и только тогда, когда НОД(a, m) = 1. Иначе он — делитель нуля: существует ненулевой [b] с [a]·[b] = [0].
Доказательство. Если НОД(a, m) = 1, по соотношению Безу as + mt = 1, и [s] — обратный. Если d = НОД(a, m) > 1, то a·(m/d) = (a/d)·m ≡ 0, причём m/d ≢ 0 — делитель нуля, а делитель нуля обратимым быть не может.
Обратимые классы образуют группу ℤₘ*. В ℤ_12: обратимы 1, 5, 7, 11, делители нуля — 2, 3, 4, 6, 8, 9, 10 (например, 3·4 = 12 ≡ 0). Если m = p простое, обратимы все ненулевые элементы: ℤₚ — поле.
Функция Эйлера
φ(m) — количество чисел от 1 до m, взаимно простых с m, то есть число элементов ℤₘ*.
- φ(p) = p − 1, φ(p^k) = p^k − p^(k−1) = p^(k−1)·(p − 1) для простого p;
- φ(ab) = φ(a)·φ(b) при НОД(a, b) = 1 (мультипликативность);
- для m = p_1^(k_1)·…·p_s^(k_s): φ(m) = m·(1 − 1/p_1)·…·(1 − 1/p_s).
Среди чисел 1, …, p^k не взаимно просты с p^k только кратные p — их p^(k−1). Мультипликативность следует из китайской теоремы: ℤ_(ab) соответствует парам (вычет mod a, вычет mod b), и обратимым элементам — пары обратимых. Пример: φ(12) = 12·(1 − 1/2)·(1 − 1/3) = 4.
Порядок элемента и первообразные корни
Порядок ord_m(a) обратимого a — наименьшее d > 0 с a^d ≡ 1 (mod m). Если ord_m(g) = φ(m), то g — первообразный корень по модулю m: его степени пробегают всю группу ℤₘ*.
- a^n ≡ 1 ⇔ ord(a) | n; в частности, ord(a) | φ(m).
- Первообразные корни существуют только для m = 1, 2, 4, p^k, 2p^k (p — нечётное простое) — теорема Гаусса. Если они есть, их ровно φ(φ(m)).
- Проверка: g — первообразный корень по модулю простого p ⇔ g^((p−1)/q) ≢ 1 (mod p) для каждого простого q | p − 1.
Почему работает проверка. Порядок g делит p − 1. Если он меньше p − 1, то он делит (p − 1)/q для некоторого простого q, и тогда g^((p−1)/q) ≡ 1. Поэтому для проверки нужно знать разложение p − 1 — для больших p лаборатория получает его вместе с доказательством простоты.
| k | 1 | 2 | 3 | 4 | 5 | 6 | порядок |
|---|---|---|---|---|---|---|---|
| 2^k | 2 | 4 | 1 | 2 | 4 | 1 | 3 |
| 3^k | 3 | 2 | 6 | 4 | 5 | 1 | 6 |
| 6^k | 6 | 1 | 6 | 1 | 6 | 1 | 2 |
3 — первообразный корень: его степени дают все ненулевые вычеты. Всего первообразных корней φ(6) = 2 — это 3 и 5. Проверка по критерию: 6 = 2·3, 3^3 = 27 ≡ 6 ≢ 1, 3^2 = 9 ≡ 2 ≢ 1.
Дискретный логарифм
Если g — первообразный корень, каждое y ∈ ℤₘ* равно g^x для единственного x из 0, …, φ(m) − 1. Это x — дискретный логарифм (индекс) y по основанию g.
Он обладает свойствами обычного логарифма по модулю φ(m): log(ab) ≡ log a + log b. Вычислять g^x легко, а находить x — трудно: перебор требует до p − 1 шагов.
Алгоритм «шаг младенца — шаг великана» (Шенкс)
Положим n = ⌈√(p − 1)⌉ и будем искать x = i·n + j, 0 ≤ i, j < n. Условие g^(in+j) = y равносильно y·(g^(−n))^i = g^j.
- Шаги младенца: вычислить и запомнить в таблице g^j для j = 0, …, n − 1.
- Шаги великана: вычислять γ_i = y·(g^(−n))^i для i = 0, 1, …, пока γ_i не найдётся в таблице.
Время и память — O(√p): для 1024-битного p это около 2^512 операций, то есть по-прежнему невозможно.
n = ⌈√6⌉ = 3. Шаги младенца: 3^0 = 1, 3^1 = 3, 3^2 = 2. g^(−3) = 6⁻¹ = 6 (mod 7). Шаги великана: γ_0 = 5 — нет в таблице; γ_1 = 5·6 = 30 ≡ 2 = 3^2. Значит, x = 1·3 + 2 = 5. Проверка: 3^5 = 243 ≡ 5 (mod 7).
Если p − 1 раскладывается только на малые простые, дискретный логарифм вычисляется быстро — задача распадается на логарифмы в маленьких подгруппах. Поэтому в криптографии p − 1 обязательно должно иметь большой простой делитель. В генераторе лаборатории это выполняется автоматически: p − 1 = R·q, где простое q имеет примерно половину длины p.
Пять примеров: классы вычетов, приведённая система и φ(m), обратимые элементы и делители нуля, порядок и первообразные корни, дискретный логарифм методом Шенкса. Открыть →
Вопросы для самопроверки
- Вычислите φ(100).
Ответ
100 = 2^2·5^2, φ = 100·(1/2)·(4/5) = 40. - Найдите все первообразные корни по модулю 11, если известно, что 2 — один из них.
Ответ
Это 2^k при НОД(k, 10) = 1: k = 1, 3, 7, 9 → 2, 8, 7, 6. - Почему по модулю 8 нет первообразных корней?
Ответ
ℤ_8* = {1, 3, 5, 7}, и квадрат каждого элемента равен 1: максимальный порядок 2, а φ(8) = 4.