Нетривиальный делитель¶
Нетривиальный делитель — это делитель натурального числа, отличный от единицы и от самого числа. Иначе говоря, делитель, который не является тривиальным. Понятие играет ключевую роль в теории чисел: число, не имеющее нетривиальных делителей, называется простым, а число, имеющее их, — составным.
¶Определение
Пусть n — натуральное число. Делителем n называется натуральное число d, на которое n делится без остатка, то есть существует натуральное k такое, что n = d · k. Всякое натуральное число имеет хотя бы два делителя: единицу и само себя. Эти два делителя называются тривиальными.
Нетривиальным делителем числа n называется любой его делитель d, такой, что 1 < d < n. Например, у числа 12 есть делители 1, 2, 3, 4, 6 и 12. Тривиальными являются 1 и 12, а нетривиальными — 2, 3, 4 и 6.
¶Связь с простыми и составными числами
Классификация натуральных чисел по наличию нетривиальных делителей лежит в основе элементарной теории чисел:
- Простое число — натуральное число больше единицы, не имеющее нетривиальных делителей. Простыми являются 2, 3, 5, 7, 11, 13, 17, 19, 23 и далее.
- Составное число — натуральное число больше единицы, имеющее хотя бы один нетривиальный делитель. К ним относятся 4, 6, 8, 9, 10, 12 и все остальные числа, кроме единицы и простых.
- Единица не является ни простым, ни составным числом: её единственный делитель — тривиальный.
Таким образом, натуральное число больше единицы либо простое, либо составное, и это разбиение однозначно определяется наличием или отсутствием нетривиальных делителей.
¶Нетривиальные делители и факторизация
Фундаментальная теорема арифметики утверждает, что любое составное число можно представить в виде произведения простых множителей, причём такое представление единственно с точностью до порядка сомножителей. Нетривиальные делители числа тесно связаны с его разложением: если n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ — каноническое разложение, то число всех делителей (включая тривиальные) равно (a₁ + 1)(a₂ + 1)…(aₖ + 1), а число нетривиальных делителей на единицу меньше.
Наличие малого нетривиального делителя — важный признак в вычислительной математике. Если число составное, то у него существует нетривиальный делитель не больше квадратного корня из числа: если n = d · k и оба множителя больше единицы, то хотя бы один из них не превышает √n. Этот факт лежит в основе простейших алгоритмов проверки на простоту — перебора делителей до √n.
¶Алгоритмы поиска нетривиальных делителей
Поиск нетривиальных делителей большого числа — нетривиальная вычислительная задача. Наиболее известные подходы:
| Алгоритм | Идея | Сложность |
|---|---|---|
| Перебор делителей | Проверка всех чисел от 2 до √n | O(√n) |
| Метод Ферма | Представление n в виде разности квадратов | Зависит от близости делителей |
| Алгоритм Полларда ρ | Детерминированная случайная функция и поиск коллизий | O(n^(1/4)) в среднем |
| Алгоритм Полларда p − 1 | Использование свойств порядка элемента | Эффективен для гладких p − 1 |
| Эллиптическая кривая | Метод Ленстры с эллиптическими кривыми | Субэкспоненциальный |
Все перечисленные алгоритмы решают задачу нахождения нетривиального делителя составного числа. Их эффективность критически важна для криптографии: безопасность RSA и ряда других систем основана на том, что разложение большого числа на простые множители (и, следовательно, поиск его нетривиальных делителей) вычислительно трудно для современных компьютеров.
¶Применение
Понятие нетривиального делителя используется в различных областях математики и информатики:
- Теория чисел — классификация чисел, изучение простых чисел, задачи делимости.
- Криптография — построение криптосистем, работающих на сложности факторизации (RSA, криптосистема Рабина).
- Алгоритмы — задачи проверки на простоту, генерация простых чисел, тесты простоты (тест Миллера — Рабина).
- Комбинаторика и теория графов — задачи о делимости, построение конструкций, использующих свойства делителей.
¶Интересные факты
Число 1 — единственное натуральное число, не являющееся ни простым, ни составным, поскольку у него нет нетривиальных делителей. Двойка — единственное простое чётное число, а значит, единственное число, у которого единственный нетривиальный «кандидат» на делитель (2) совпадает с самим числом, что делает его простым.
Число 6 — наименьшее составное число, у которого все нетривиальные делители (2 и 3) являются простыми, а само оно равно их произведению. Число 4 — наименьшее составное число, у которого нетривиальный делитель (2) не является простым множителем в разложении на простые множители в том смысле, что 4 = 2², и делитель 2 повторяется.
¶Источники
- Новиков П. С. «Элементы теории чисел»
- Виноградов И. М. «Основы теории чисел»
- Кнут Д. «Искусство программирования», том 2
- Ривест Р., Шамир А., Адлеман Л. «Метод получения цифровой подписи» (RSA, 1978)
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»