Делимость и простые числа

RSA-2048 защищает транзакции объёмом 5 триллионов долларов в день. Сломать RSA-2048 - значит разложить число из 617 цифр на два простых множителя. Лучший суперкомпьютер на Земле потратит на это $10^{15}$ лет. Для сравнения: возраст Вселенной - $1.4 \times 10^{10}$ лет. Простые числа, которые Евклид изучал из чистого любопытства в 300 году до н.э., сегодня стоят между хакером и вашим банковским счётом.

• **RSA-шифрование**: каждое HTTPS-соединение генерирует пару простых по 1024-2048 бит. Перемножить - миллисекунда. Разложить обратно - $10^{15}$ лет на любом существующем железе.
• **Bitcoin-адреса**: генерируются через ECDSA поверх эллиптических кривых над полями из простых чисел. Каждый кошелёк - это точка на кривой над $\mathbb{F}_p$, где $p$ - 256-битное простое.
• **Хеш-таблицы**: размер таблицы выбирают простым, чтобы минимизировать коллизии. SHA-256 внутри - арифметика по простым модулям.
• **Криптографические генераторы случайных чисел**: Blum Blum Shub, ChaCha20 - все строятся на простых числах как на фундаменте.

Divisibility

Числа делятся не все на все. Это видно сразу. А вот что не видно: отношение делимости порождает целую алгебраическую структуру - решётку. И именно из неё вырастает RSA. Говорят «a делит b» (пишут $a \mid b$), если существует целое $k$ такое, что $b = a \cdot k$. Без остатка, без округления, ровно.

**Делимость:** a | b ⟺ ∃ k ∈ ℤ : b = a · k Примеры: 3 | 12 (12 = 3 · 4), 7 | 0 (0 = 7 · 0), 1 | n для любого n. **Деление с остатком:** для любых a, b (b > 0) существуют единственные q, r: a = b · q + r, где 0 ≤ r < b q - неполное частное, r - остаток.

Свойства делимости: 1. $a \mid a$ - рефлексивность 2. если $a \mid b$ и $b \mid c$, то $a \mid c$ - транзитивность 3. если $a \mid b$ и $a \mid c$, то $a \mid (b \pm c)$ 4. линейная комбинация: если $a \mid b$ и $a \mid c$, то $a \mid (bx + cy)$ для любых целых $x, y$. Последнее свойство - сердце алгоритма Евклида.

Делимость - не школьная арифметика. Отношение $a \mid b$ задаёт частичный порядок на натуральных числах. Диаграмма Хассе этого порядка - визуальная карта всех делителей. В ML эта идея всплывает неожиданно: топологическая сортировка графа вычислений в autograd PyTorch - это обход диаграммы Хассе DAG-зависимостей.

Primes

Простые числа - атомы арифметики. Число $p > 1$ простое, если делится только на 1 и само на себя. $2, 3, 5, 7, 11, 13, \ldots$ - простые. $4 = 2 \cdot 2$ - составное. $1$ - ни то ни другое (об этом отдельно). Простота - это не редкость: среди первых миллиона натуральных чисел 78498 простых. Но среди чисел вблизи $10^{1000}$ - один шанс на $2300$. Именно это разрежение делает RSA безопасным.

**Простое число** p > 1: его единственные делители - 1 и p. **Составное число** n > 1: существует делитель d, 1 < d < n. **Теорема Евклида (III в. до н.э.):** простых чисел бесконечно много. Доказательство: допустим, простых конечно много: p₁, p₂, ..., pₙ. Рассмотрим N = p₁ · p₂ · ... · pₙ + 1. Число N не делится ни на одно pᵢ (остаток 1). Значит, N либо простое, либо имеет простой делитель, не входящий в список. Противоречие.

Распределение простых описывается **Prime Number Theorem**: количество простых до $N$ примерно $N / \ln N$. Среди первого миллиона - 78498 простых (теорема даёт $\approx 72382$, погрешность ~8%). Простые разрежаются с ростом $N$, но никогда не заканчиваются. И этот «редкий» товар - единственный строительный материал для RSA-ключей.

Fundamental Theorem

Основная теорема арифметики (Fundamental Theorem of Arithmetic) утверждает: каждое натуральное $n > 1$ раскладывается в произведение простых, и это разложение **единственно** с точностью до порядка. Именно единственность делает простые числа атомами. Если бы разложение не было единственным - RSA не работал бы, потому что шифр основан на том, что по открытому ключу $n = p \cdot q$ невозможно найти $p$ и $q$.

**Основная теорема арифметики:** для любого n > 1 существует единственное разложение: n = p₁^{a₁} · p₂^{a₂} · ... · pₖ^{aₖ} где p₁ < p₂ < ... < pₖ - простые, aᵢ ≥ 1. Примеры: - 360 = 2³ · 3² · 5 - 1001 = 7 · 11 · 13 - 2024 = 2³ · 11 · 23

Из разложения на простые следуют формулы для: количества делителей $d(n) = \prod (a_i + 1)$, суммы делителей $\sigma(n) = \prod (p_i^{a_i+1} - 1)/(p_i - 1)$, функции Эйлера $\varphi(n) = n \cdot \prod (1 - 1/p_i)$. Функция Эйлера $\varphi(n)$ - именно то, что используется в RSA при вычислении закрытого ключа: $d \equiv e^{-1} \pmod{\varphi(n)}$. Вся мультипликативная теория чисел строится на этом фундаменте.

Единственность разложения - не банальный факт. В кольце $\mathbb{Z}[\sqrt{-5}]$ единственность **нарушается**: $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ - два разных разложения на неприводимые. Куммер и Дедекинд создали теорию идеалов в XIX веке именно для того, чтобы вернуть единственность в эти «сломанные» кольца. Это ответвление дало начало всей современной алгебраической теории чисел.

Sieve

Решето Эратосфена - алгоритм, который находит **все** простые до $N$ за $O(N \log \log N)$ операций. Придуман в III веке до н.э. и до сих пор не устарел - именно его используют криптографические библиотеки (OpenSSL, libsodium) при генерации простых для RSA-ключей. Идея: выписываем числа от 2 до $N$, вычёркиваем кратные 2, кратные 3, кратные 5 - и так до $\sqrt{N}$. Невычеркнутые - простые.

**Алгоритм решета Эратосфена:** 1. Создать массив [2, 3, 4, ..., N], пометить все как «возможно простые» 2. Взять наименьшее непомеченное число p (начиная с 2) 3. Вычеркнуть все кратные p: 2p, 3p, 4p, ... (начиная с p²) 4. Повторять шаги 2-3, пока p² ≤ N 5. Оставшиеся невычеркнутые - простые числа **Сложность:** O(N log log N) - почти линейная

Ключевая оптимизация: вычёркивание начинается с $p^2$, не с $2p$. Почему? Всё, что меньше $p^2$, уже вычеркнуто на предыдущих шагах. При $p = 5$ число $10 = 2 \cdot 5$ вычеркнуто ещё на шаге $p = 2$, $15 = 3 \cdot 5$ - на шаге $p = 3$. Первое «новое» составное - $25 = 5^2$. Это снижает число операций с $O(N)$ до $O(N \log \log N)$.

Сегодня решето живёт в двух модификациях: сегментированное (вместо одного массива - блоки по $\sqrt{N}$, экономия памяти) и решето Аткина (теоретически быстрее, но на практике часто медленнее из-за накладных расходов). Для генерации RSA-ключей используют другое: решето + вероятностный тест Миллера-Рабина. Из $10^9$ кандидатов отсеиваем решетом составные, остатки проверяем на вероятностную простоту за миллисекунды.

Ключевые идеи

• **Делимость** $a \mid b$: $b = a \cdot k$; деление с остатком: $a = b \cdot q + r$, $0 \le r < b$
• **Простые числа** - атомы арифметики: делятся только на 1 и себя; бесконечно много (Евклид, ~300 до н.э.)
• **Основная теорема арифметики:** каждое $n > 1$ раскладывается на простые единственным образом - именно поэтому RSA работает
• **Решето Эратосфена:** $O(N \log \log N)$ - 2200-летний алгоритм, до сих пор используемый в криптографических библиотеках
• **Простые числа и безопасность:** Евклидова эстетика из 300 до н.э. стала фундаментом банковской защиты мирового масштаба

Связанные темы

Делимость и простые числа - фундамент для:

• Алгоритм Евклида и НОД — GCD - ключевая операция над делимостью, связанная с простым разложением
• Модулярная арифметика — Остатки от деления формируют алгебраическую структуру, центральную для криптографии

Вопросы для размышления

• AKS-тест проверяет простоту за полиномиальное время - тогда почему факторизация считается вычислительно трудной? В чём разница между «проверить, простое ли» и «разложить на множители»?
• Алгоритм Шора для квантовых компьютеров факторизует RSA-2048 за часы, не тысячелетия. Что именно сломается в современном интернете и что уже делают криптографы прямо сейчас (post-quantum cryptography)?
• Гипотеза о простых-близнецах ($p$ и $p+2$ - оба простые) не доказана 2000 лет. В 2013 Чжан Итан доказал, что таких пар с разностью $\le 70{,}000{,}000$ бесконечно много. Что это говорит о распределении простых?

Связанные уроки

• crypto-03-number-theory