Теория
Факторизация — разложение числа на простые множители. Для небольших чисел работает пробное деление, но для чисел с десятками знаков перебор делителей занял бы годы. Большие числа раскладывают специальными алгоритмами, из которых самый известный — метод Полларда Rho.
Идея метода: строят последовательность \(x_{i+1} = x_i^2 + c \pmod n\). Она зацикливается, и по форме цикла (напоминающей букву ρ) находят нетривиальный делитель через НОД разности двух членов последовательности с числом \(n\). Алгоритм вероятностный, но на практике очень быстр: ему под силу числа до \(10^{18}\) и больше.
Важно: если число простое, метод делителя не найдёт — тогда калькулятор просто сообщит, что число простое.
Пример с решением
- Условие. Разложите число 8051 на множители.
- Формула. Метод Полларда Rho: \(x_{i+1} = x_i^2 + c \pmod n\), делитель — НОД разностей членов с \(n\).
- Подстановка. Последовательность с \(x_0 = 2\), \(c = 1\) быстро даёт делитель 83.
- Вычисление. \(8051 \div 83 = 97\); 97 — простое.
- Ответ. \(8051 = 83 \times 97\). Калькулятор с полем 8051 покажет ровно это разложение; для простого числа выведет «простое».
Главное
- Пробное деление работает до \(\sqrt{n}\), но для больших чисел слишком медленно.
- Поллард Rho — вероятностный метод, раскладывает числа до \(10^{18}\) за доли секунды.
- Делители проверяются на простоту и при необходимости раскладываются дальше.