Теория чисел
Теория чисел изучает целые числа и арифметические структуры, построенные на них: делимость, простые числа, сравнения по модулю и решения уравнений в целых числах. Например, сравнение по модулю описывает остаток и позволяет формализовать периодические закономерности вроде дней недели.
В классическом изложении различают элементарные, алгебраические и аналитические методы; криптография использует лишь часть результатов, поэтому теорию чисел нельзя сводить к RSA.
Теория чисел
Простые числа
Простое число — натуральное число больше единицы, имеющее ровно два положительных делителя: единицу и само себя. Простые числа служат множителями в разложении целых чисел; их поиск, проверка простоты и распределение являются отдельными задачами теории чисел.
Делимость
Свойства деления целых чисел. НОД (алгоритм Евклида, ~300 до н.э.), НОК. Основная теорема арифметики: любое число разложимо на простые множители единственным способом. Признаки делимости: на 2 (последняя цифра чётная), на 3 (сумма цифр), на 9.
Сравнения по модулю
a ≡ b (mod m) если m | (a−b). Малая теорема Ферма: a^p ≡ a (mod p) для простого p. Китайская теорема об остатках (решение систем сравнений). Применение: RSA-криптография (1977, Ривест-Шамир-Адлеман), хеш-функции.
Малая теорема Ферма
Если p простое и gcd(a, p) = 1, то aᵖ⁻¹ ≡ 1 (mod p). Fermat, 1640. Следствие: aᵖ ≡ a (mod p) для любого a. Применение: быстрое возведение в степень по модулю, тест простоты. Обобщение: теорема Эйлера для φ(n). Основа RSA-криптографии.
Китайская теорема об остатках
Система сравнений x ≡ aᵢ (mod nᵢ) имеет единственное решение по модулю N = ∏nᵢ, если nᵢ попарно взаимно просты. Происхождение: Sun Tzu, III век. Алгоритм: расширенный Евклид. Применение: ускорение RSA, календарные вычисления, секретное разделение (Shamir).