Конспект: модульная арифметика, НОД и обратный элемент

Понятия

Сравнимы по модулю m - дают одинаковый остаток при делении на m; a ≡ b (mod m). То же самое: a − b делится на m.

НОД - наибольшее число, на которое делятся оба. Взаимно простые - числа с НОД, равным единице.

Обратный элемент к a по модулю m - число x с a · x ≡ 1 (mod m). Делить на a - значит умножать на него.

Функция Эйлера φ(m) - сколько чисел от 1 до m взаимно просты с m. φ(p) = p − 1, φ(p · q) = (p − 1)(q − 1).

Что унести

ЧТО МОЖНО ПО МОДУЛЮ
сложение, вычитание, умножение     всегда; остаток можно брать после любого действия
деление на a                       только если НОД(a, m) = 1: умножить на обратный
сокращение a·c ≡ b·c на c          только если НОД(c, m) = 1
сравнение «больше-меньше»          никогда: остатки не упорядочены

АЛГОРИТМ ЕВКЛИДА                         РАСШИРЕННЫЙ
пока b ≠ 0:                              ведём пару (x, y):  число = x · a₀ + y · b₀
    a, b = b, a mod b                    старт: a₀ → (1, 0),  b₀ → (0, 1)
ответ: a                                 новая пара = старая − q · следующая
                                         в конце:  a₀ · x + b₀ · y = НОД

1989, 867:  2·867+255 → 3·255+102 → 2·102+51 → 2·51+0        НОД = 51, 4 круга
40, 7:      3 · 40 − 17 · 7 = 1        обратный к 7 по модулю 40:  −17 + 40 = 23

Худший вход Евклида - соседние числа Фибоначчи. Все частные равны единице. Версия на вычитании на паре (1 000 000, 1) делает 999 999 кругов - экспонента по числу цифр.

СРАВНЕНИЕ a · x ≡ b (mod m),   g = НОД(a, m)
b не делится на g    →  решений нет               6x ≡ 4 (mod 9)
b делится на g       →  решений ровно g           6x ≡ 3 (mod 9):  2, 5, 8
как решать:  поделить a, b и m на g;  x ≡ (b/g) · (a/g)⁻¹  по модулю m/g

СТЕПЕНЬ ПО МОДУЛЮ                        показатель     кругов    шагов
r = 1                                    10³              10        62
пока n > 0:                              10⁹              30       169
    если n нечётно: r = r · a mod m      10¹⁵             50       276
    a = a · a mod m                      кругов = ⌊log₂ n⌋ + 1
    n = n // 2                           цикл «умножай n раз»: 3 000 004 шага на 10⁶

Малая теорема Ферма. p простое, a не делится на p → a^(p−1) ≡ 1 (mod p). Теорема Эйлера. НОД(a, m) = 1 → a^φ(m) ≡ 1 (mod m).

следствия:   показатель берётся по модулю p − 1       3^(10¹²) mod 1 000 003 = 3⁴ = 81
             обратный по простому модулю = a^(p−2)    цена та же, что у Евклида: 114 и 120 шагов
обратное неверно:   3⁹⁰ mod 91 = 1,  а 91 = 7 · 13

КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ             модули попарно взаимно просты, M - их произведение
x = Σ rᵢ · Mᵢ · (Mᵢ⁻¹ mod mᵢ)  mod M      Mᵢ = M / mᵢ
остатки 2, 3, 2 по модулям 3, 5, 7:   2 · 70 + 3 · 21 + 2 · 15 = 233 → 23
условие: настоящий ответ меньше M, иначе соберётся его остаток

В Python: math.gcd(a, b), pow(a, n, m), pow(a, -1, m) с версии 3.8. Не a ** n % m.

Линейное сравнение: d = НОД(a,m) должен делить b; затем реши по модулю m/d и верни d ответов с шагом m/d.

Ловушки джокера

Остаток взят в конце. Числа успевают вырасти: в Python - квадрат вместо линии, в C - переполнение.

Модуль больше корня из предела типа. Произведение двух остатков доходит до m². На тренажёре модуль не больше 94 906 265, в 64 битах - не больше 2³².

Отрицательный остаток. В C, Java, JavaScript -7 % 5 равно -2. Брать (x % m + m) % m.

Деление остатков напрямую. (a / b) mod m - это a · b⁻¹, а не (a mod m) // (b mod m).

Обратный без проверки НОД. Для пары (6, 9) коэффициент есть - 8, - а обратного нет: 6 · 8 ≡ 3.

Коэффициент не приведён. Расширенный Евклид отдаёт −17, а не 23.

Показатель по модулю p. Круг имеет длину p − 1: 2¹⁰ mod 7 = 2, а 2³ mod 7 = 1.

Основание, кратное модулю. Теорема Ферма к нему не относится: все степени нулевые.

Единица как доказательство простоты. 3⁹⁰ mod 91 = 1, но 91 составное.

НОК через произведение. a * b // НОД переполняется; считать a // НОД * b.

Китайская теорема с общим делителем у модулей. x ≡ 1 (mod 4), x ≡ 2 (mod 6) несовместны.

Ответ больше произведения модулей. Собирается не он, а его остаток - число, ни на что не похожее.

Время степени зависит от битов показателя. Если показатель секретен, домножение «только на единичных битах» выдаёт его по времени ответа.

Куда это ведёт

Теорема Ферма работает в одну сторону: у простого модуля степень p − 1 всегда даёт единицу. Значит, если для числа n нашлось основание, у которого aⁿ⁻¹ - не единица, то n составное, и доказано это без единого делителя. Следующая глава превращает это наблюдение в проверку простоты для чисел в сотни цифр - и разбирается с числами вроде 91, которые умеют притворяться.