Конспект раздела: числа и алгебра

Карта раздела

        ДЛИНА ЧИСЛА - ВРАГ                              ДЛИНА ЗАПЕРТА МОДУЛЕМ
  число = список разрядов                    остаток после каждого действия
  сложение n, умножение n²        ───────►   + − × всегда;  деление = обратный элемент
  размер входа = число разрядов              Евклид: 5 кругов на цифру
            │                                степень: кругов = битов показателя
            │                                Ферма: a^(p−1) ≡ 1, p ∤ a;  китайская теорема
            ▼                                              │
  √N шагов - экспонента                                    ▼
            │                                ЛЕГКО: простое ли число (Миллер-Рабин, 1/4ᵏ)
            └──────────────────────────────► ТРУДНО: на что оно делится (ро-метод: √p)
                                                           │
                                                           ▼
                                             обмен ключами, RSA, подпись:
                                             лёгкое - своим, трудное - чужим

        ДРОБНЫЕ ЧИСЛА: цена известна, доверие - нет
  метод Гаусса n³  →  выбор ведущего элемента  →  LU: n³ один раз, n² на правую часть
  16 значащих цифр;  плохая обусловленность не лечится;  по простому модулю - точно

Дерево решений: числовая задача - подходящий инструмент

Число не помещается в машинное слово?
├─ нужен только остаток           → брать остаток после каждого действия
├─ нужно число целиком            → список разрядов; основание с машинное слово
└─ длина в тысячи разрядов        → Карацуба, преобразование Фурье (раздел 13)

Общий делитель, сокращение, НОК?  → алгоритм Евклида
Разделить по модулю?              → расширенный Евклид; НОД ≠ 1 - обратного нет
Степень по модулю?                → квадраты по битам показателя; pow(a, n, m)
Огромный показатель, модуль прост? → показатель по модулю p − 1
Несколько модулей сразу?          → китайская теорема, модули взаимно
                                  просты; ответ один среди меньших произведения

Все простые до N?                 → решето Эратосфена, N до миллиардов
Простое ли одно большое число?    → Миллер-Рабин; до 3 · 10²³ - двенадцать оснований точно
Разложить на множители?           → перебор до корня; ро-метод; дальше - только рекорды

Общий секрет по открытому каналу? → обмен Диффи-Хеллмана + подпись
Письмо тому, кого нет на связи?   → ключ сеанса под открытым ключом, данные - быстрым шифром
Подтвердить автора?               → подпись под хешем

Система линейных уравнений?       → метод Гаусса с выбором ведущего элемента
Много правых частей?              → LU-разложение
Нужен точный ответ?               → по простым модулям + китайская

Главные замеры раздела

что	замер
число Фибоначчи № 1600 списком разрядов	2 429 220 шагов, в 223 раза дороже № 100
умножение столбиком, `n = 400`	803 209 шагов; формула `5n² + 8n + 9`
`3⁸⁰⁰` целиком: 800 умножений против 12	618 293 и 283 942 - всего в 2,2 раза
перебор делителей, простое из 10 цифр	299 998 шагов; каждые две цифры вдесятеро
алгоритм Евклида, случайные числа по 15 цифр	29,3 круга в среднем, 44 самое большее
Евклид на вычитании, пара `(1 000 000, 1)`	999 999 кругов
`3` в степени `10¹⁵` по модулю	50 кругов, 276 шагов
решето до миллиона	78 498 простых, 2,1 вычёркивания на число
лжецы у 561: Ферма и Миллер-Рабин	320 из 320 взаимно простых и 10 из 560
Миллер-Рабин против перебора, 8 цифр	185 и 29 999 шагов
ро-метод против перебора, делитель из 7 цифр	314 771 и 29 999 918 шагов
дискретный логарифм, `p ≈ 10⁶`	перебор 2 333 358, встреча посередине 10 973
ключ RSA из 53 бит	собрать 1 674, зашифровать 19, расшифровать 52
метод Гаусса, `n = 80`	541 250 шагов; вдвое больше уравнений - в восемь раз
матрица Гильберта, `n = 13`	ошибка 4,2 при невязке `9 · 10⁻¹⁶`

Что проверять в своём коде

Границы типа. Где число может перерасти 64 бита или 2⁵³? Произведение двух остатков - до m².

Остаток - после каждого умножения, а не в конце. В других языках - (x % m + m) % m.

От чего считана оценка. √N, N / 2 - экспонента по числу цифр.

Деление по модулю. Только через обратный и только после проверки НОД.

Ответ теста простоты. «Составное» - доказательство, «простое» - вероятность. Для чужих чисел основания случайные.

Криптография - из библиотеки. Формула mᵉ mod n - малая часть схемы; дополнение, случайность и проверки делает библиотека.

Случайность для ключей - secrets, а не random.

Дробные числа. Нет ==; есть выбор ведущего элемента; невязке не верить; деньги - в целых.

Чужой ввод. Длина числа ограничивается до разбора: перевод в десятичную запись квадратичен.

Когда перебор шагов заменяется алгеброй

Задача	Инструмент	Условие или граница
a·x ≡ b (mod m)	Расширенный Евклид	При d=НОД(a,m) решение есть ровно при d, делящем b; ответов по модулю m ровно d.
Линейная рекуррента порядка k	Степень матрицы перехода	При обычном умножении O(k³ log n) арифметических действий; длина чисел учитывается отдельно.

Объясни своими словами

Почему n сложений могут стоить n² и где в программе этого не видно.
Почему быстрая степень без модуля почти не выигрывает, а с модулем выигрывает на порядки.
Почему общие делители пар (a, b) и (b, a mod b) совпадают.
Откуда расширенный алгоритм Евклида берёт обратный элемент и когда его не существует.
Почему a^(p−1) ≡ 1 по простому модулю - через перестановку остатков.
Что именно тест Миллера-Рабина ищет в цепочке квадратов и почему у простого числа этого нет.
Почему проверить простоту легко, а разложить трудно, - и что из этого следует для шифрования.
Почему (mᵉ)ᵈ возвращает m и что мешает постороннему найти d.
Зачем подписывают хеш, а не сообщение.
Чем маленький ведущий элемент отличается от плохой обусловленности и что из них лечится.

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

Раздел работал с числом как с величиной. Следующий смотрит на то же число как на набор битов: маски вместо множеств, счёт единиц без цикла, арифметика без ветвлений, деление на константу умножением. Это слой, на котором живут компиляторы и внутренности структур данных, - и на котором числа из этого раздела хранятся на самом деле.