Теория чисел

Теория чисел — раздел математики, изучающий свойства целых чисел: делимость, простые числа, сравнения по модулю, диофантовы уравнения. Зародилась в Древней Греции (Евклид доказал бесконечность простых, 300 до н.э.). Ферма, Эйлер, Гаусс развили в XVII-XIX веках. Сегодня — основа криптографии RSA.

Простые числа — кирпичики арифметики. Любое число раскладывается на простые: 12 = 2 × 2 × 3. Казалось бы, чистая абстракция. Но в 1977 году Ривест, Шамир, Адлеман создали RSA — защиту банковских карт на простых числах. Сегодня каждая HTTPS-транзакция использует теорию чисел.

Простые числа: бесконечность и распределение

Простое число делится только на 1 и себя: 2, 3, 5, 7, 11, 13... Евклид (300 до н.э.) доказал: простых чисел бесконечно много. Доказательство от противного: если конечно, умножим все и прибавим 1 — получим новое простое.

Решето Эратосфена (III век до н.э.) — древний алгоритм поиска простых. Вычеркиваем кратные 2, затем 3, 5, 7... Остаются простые. Работает, но медленно для больших чисел.

Распределение простых: нерегулярное, но есть закономерность. Теорема о распределении простых (доказана 1896, Адамар и Валле-Пуссен): количество простых до N примерно N / ln(N). До миллиона — 78 498 простых.

Проблема близнецов: бесконечно ли пар простых с разностью 2 (3-5, 11-13, 17-19)? Открыта 2300 лет, до сих пор не решена. Премия $1 млн за доказательство.

Делимость и НОД

Наибольший общий делитель (НОД) чисел a и b — наибольшее число, делящее оба. НОД(12, 18) = 6. Алгоритм Евклида (300 до н.э.) находит НОД за log(N) шагов: делим большее на меньшее, заменяем большее на остаток, повторяем.

Пример: НОД(48, 18). 48 = 18 × 2 + 12. 18 = 12 × 1 + 6. 12 = 6 × 2 + 0. Ответ: 6.

Взаимно простые числа: НОД = 1. Пример: 9 и 14. Важно для RSA: открытый и закрытый ключи взаимно просты с φ(n).

Модульная арифметика: часы математики

Сравнение по модулю: a ≡ b (mod m), если a − b делится на m. 17 ≡ 5 (mod 12), потому что 17 − 5 = 12.

Часовая аналогия: 17 часов = 5 часов вечера (модуль 12). Компьютеры считают по модулю 2^32 или 2^64.

Малая теорема Ферма (1640): если p — простое и НОД(a, p) = 1, то a^(p−1) ≡ 1 (mod p). Пример: 2^6 ≡ 1 (mod 7). Основа RSA и тестов простоты.

Китайская теорема об остатках (III век н.э.): система x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) имеет единственное решение по модулю m₁ × m₂, если m₁ и m₂ взаимно просты. Используется в RSA для ускорения расшифровки в 4 раза.

RSA-криптография: теория чисел защищает интернет

Алгоритм RSA (1977) основан на сложности факторизации. Легко умножить простые p × q = n. Но разложить n обратно — задача NP (миллионы лет для 2048-битных чисел).

Ключи RSA: открытый (e, n), закрытый (d, n). Шифрование: c = m^e mod n. Расшифровка: m = c^d mod n. Работает благодаря малой теореме Ферма: выбираем d так, что ed ≡ 1 (mod φ(n)).

Каждая транзакция в банкомате, каждое HTTPS-соединение (зелёный замок в браузере) использует RSA. Без теории чисел онлайн-банкинг невозможен.

Диофантовы уравнения

Уравнения в целых числах. Пример: x² + y² = z² (Пифагоровы тройки). Решения: (3, 4, 5), (5, 12, 13), (8, 15, 17)...

Великая теорема Ферма (1637): x^n + y^n = z^n не имеет решений для n > 2. Ферма записал на полях книги: «У меня есть замечательное доказательство, но поля слишком узки». Доказана Эндрю Уайлсом только в 1995 году (358 лет спустя).

Применения

Хеш-функции: SHA-256 использует простые числа для генерации псевдослучайных констант. Биткойн-майнинг — поиск хеша с нулями в начале.

Тесты простоты: Миллер-Рабин (1980) проверяет простоту вероятностно. Для 2048-битного числа — секунды вместо лет детерминированной проверки.

Случайные числа: Линейный конгруэнтный генератор: x(n+1) = (a × x(n) + c) mod m. Выбор a, c, m — из теории чисел для хорошей случайности.