Простые множители¶

Простые множители — натуральные числа, делящие заданное натуральное число без остатка; к простым множителям числа относятся все простые числа, входящие в его каноническое разложение. Например, простые множители числа 60 — это 2, 3 и 5, поскольку 60 = 2² × 3 × 5. Понятие является фундаментальным для элементарной теории чисел и находит применение в криптографии, алгоритмах и компьютерной алгебре.

¶Определение и основные свойства

Пусть n — натуральное число, n > 1. По теореме о каноническом разложении существует и единственна запись вида

n = p₁^α₁ × p₂^α₂ × … × p_k^α_k,

где p₁ < p₂ < … < p_k — попарно различные простые числа, а α₁, α₂, …, α_k — положительные целые показатели. Множества {p₁, p₂, …, p_k} — это и есть множество простых множителей числа n, а сами числа p_i называют каноническими (или примарными) множителями.

Основные свойства:

• Каждое число больше единицы имеет хотя бы одного простого множителя (следствие фундаментальной теоремы арифметики).
• Простое число имеет ровно одного простого множителя — само себя.
• Число 1 не имеет простых множителей по определению.
• Количество простых множителей числа n обозначают ω(n) (число различных простых делителей) или Ω(n) (с учётом кратности, то есть Ω(n) = α₁ + α₂ + … + α_k).

¶Алгоритмы нахождения простых множителей

¶Разложение методом пробных делений

Наиболее элементарный способ — последовательное деление числа n на простые числа 2, 3, 5, 7, … до тех пор, пока делитель не превысит √n. Если после деления на все простые до √n остаток больше единицы, то этот остаток сам является простым множителем. Сложность алгоритма составляет порядка O(√n), что делает его пригодным лишь для чисел сравнительно небольшой разрядности.

¶Алгоритм Полларда ρ

Метод Полларда ρ, предложенный Джоном Поллардом в 1975 году, находит нетривиальный делитель числа за счёт детерминированной псевдослучайной последовательности x_{i+1} = x_i² + c (mod n) и вычисления наибольшего общего делителя разностей |x_i − x_j|. Средняя сложность составляет примерно O(n^{1/4}), что существенно превосходит метод пробных делений для чисел с малым простым множителем.

¶Эллиптическая кривая

Метод кривых Полларда (ECM), разработанный в 1987 году, использует арифметику эллиптических кривых над кольцом вычетов Z/nZ. Алгоритм особенно эффективен для нахождения простых множителей небольшой разрядности, входящих в состав гигантских чисел.

¶Общие алгоритмы разложения

Для полного разложения больших чисел применяют комбинацию методов: сначала отсеивают малые простые множители пробными делениями, затем используют алгоритм Полларда ρ и ECM, а для оставшихся крупных множителей — квадратичное решето (QS) или обобщённое решето числового поля (GNFS). На 2024 год GNFS остаётся самым быстрым общим алгоритмом; с его помощью были разложены числа рекордной разрядности.

¶Теоретико-числовые функции, связанные с простыми множителями

Значения d(n) и σ(n) выражаются через показатели канонического разложения: d(n) = (α₁+1)(α₂+1)…(α_k+1), σ(n) = ∏ (p_i^{α_i+1} − 1)/(p_i − 1).

¶Применение

¶Криптография

Безопасность алгоритма RSA основана на предположении о трудности разложения на простые множители больших составных чисел (произведения двух простых чисел длиной в сотни цифр). Сходный принцип лежит в основе криптосистемы Диффи — Хеллмана и ряда других протоколов.

¶Числовые системы и сжатие данных

Понятие простых множителей используется при построении свёрточных кодов, в алгоритмах сжатия и в методах контроля целостности данных.

¶Математика

Простые множители входят в определение простых чисел, участвуют в доказательстве бесконечности множества простых, лежат в основе гипотезы Римана и исследований распределения простых чисел.

¶История

Учение о разложении чисел на простые множители восходит к работам Евклида («Начала», книга IX, ок. 300 года до н. э.), где была доказана фундаментальная теорема арифметики и бесконечность множества простых чисел. Систематическое развитие теория получила в трудах Пьера де Ферма, Леонарда Эйлера, Карла Фридриха Гаусса и Бернард Римана в XVIII–XIX веках.

¶Источники

• Виноградов И. М. Основы теории чисел
• Новосёлов А. А. Элементарная теория чисел
• Кнут Д. Искусство программирования, том 2
• Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers
• Crandall R., Pomerance C. Prime Numbers: A Computational Perspective