Разложение на множители

RSA-2048: 617 цифр, 10 квадриллионов лет на разложение. Банки защищены основной теоремой арифметики. Простые числа - атомы арифметики, и сложность их поиска охраняет интернет.

• RSA/ECC: HTTPS, TLS, SSH - весь интернет шифруется через разложение на простые
• Python hashlib, OpenSSL: генерация простых чисел через тест Миллера-Рабина прямо в производственных системах
• Pollard's rho в factordb.com: база факторизаций известных чисел, используется в математических исследованиях

Основная теорема арифметики: уникальность разложения

RSA-2048: чтобы взломать шифрование банка, нужно разложить число из 617 цифр на два простых множителя. На лучших суперкомпьютерах это займёт порядка 10 квадриллионов лет. Защита основана на одном факте: разложение на множители вычислительно трудно, а проверка - легко.

**Основная теорема арифметики**: каждое натуральное число n > 1 единственным образом (с точностью до порядка) представляется в виде произведения простых чисел.

Простые числа - атомы арифметики. 12 = 2² × 3. 360 = 2³ × 3² × 5. 97 = 97 (простое). Разложение всегда существует и всегда единственно.

Число делителей n = p1^e1 * ... * pk^ek равно (e1+1)(e2+1)...(ek+1). У 360 = 2³*3²*5 делителей: (3+1)(2+1)(1+1) = 24. Это следствие единственности разложения - не нужно перебирать все числа до n.

Решето Эратосфена и алгоритм Полларда

Пробное деление работает за O(sqrt(n)) - для n из 10 цифр это ~100K делений. Для числа из 100 цифр - уже ~10^50 операций: несолидный возраст Вселенной. Нужны умные алгоритмы.

**Решето Эратосфена**: нахождение всех простых до N за O(N log log N). Идея: вычеркнуть все кратные 2, затем 3, 5, ... - остаются только простые.

**Алгоритм Полларда (rho)**: для разложения больших чисел. Использует идею «парадокса дней рождения»: среди sqrt(p) случайных чисел ожидается коллизия по модулю p. Работает за O(n^{1/4}) - намного быстрее пробного деления.

Рекорд разложения: RSA-250 (829 бит, 250 десятичных цифр) разложен в 2020 году за 2700 процессорных лет. RSA-2048 (617 цифр) по текущим оценкам потребует 10^15 процессорных лет. Квантовый компьютер с алгоритмом Шора сделает это за полиномиальное время - поэтому разрабатывается пост-квантовая криптография.

RSA: асимметричное шифрование на простых числах

RSA (Rivest-Shamir-Adleman, 1977): выбрать два больших простых p, q. N = pq - открытый ключ. Закрытый ключ зависит от p и q. Сложность взлома - разложение N.

LCM в RSA: в современных реализациях (RFC 8017) используется lambda(N) = lcm(p-1, q-1) вместо phi(N). Это даёт меньший закрытый ключ при той же безопасности. НОД и НОК появляются прямо в центре криптографии.

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

• Основная теорема: n = p1^e1 * ... * pk^ek - единственно (атомарность простых)
• Число делителей: (e1+1)(e2+1)...(ek+1) - из разложения напрямую
• Решето Эратосфена: все простые до N за O(N log log N)
• Пробное деление: O(sqrt(n)) - до ~10^8; Полларда: O(n^{1/4}) - до ~10^18
• RSA: N = pq, защита = сложность разложения N при неизвестных p,q

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

Разложение на простые - основа теории делимости и криптографии:

• НОД (GCD) — gcd(a,b) вычисляется через разложения: gcd = произведение общих простых в минимальных степенях
• НОК (LCM) — lcm(a,b) = ab/gcd(a,b); lcm = произведение общих простых в максимальных степенях

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

• crypto-03-number-theory