Ρ-алгоритм Полларда
Материал из Википедии — свободной энциклопедии
ρ-aлгоритм Дж. Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основан на том, что вычисляется некий многочлен степени не выше второй от начального числа Х — f(X).
[править] Описание алгоритма
- Шаг 1. Выбираем многочлен f(x) с целочисленными коэффициентами и целое число m.
- Шаг 2. Случайно выбираем x0 от 0 до n и, вычисляя значения xi = f(xi − 1)modn,i = 1,...,m, проверяем тест шага 3.
- Шаг 3. Для h = 0,1,...,[logm] полагаем j = 2h − 1 и для каждого 2h < = k < 2h + 1 вычисляем d=НОД(x_j − x_k, n). Если 1 < d < n, то нетривиальный делитель числа n найден. Если d=1 или d=n, то переходим к следующему значению h.
while (gcd(X - Y) == 1) {
Y = X;
X = f(X);
X = f(X);
}
return gcd(X - Y);
В качестве многочлена f(X) можно взять, например, X2 − 1
[править] Сложность алгоритма
Пусть n — составное число. Тогда существует такая константа C, что для любого положительного числа λ вероятность события, состоящего в том, что ρ-метод Полларда не найдет нетривиального делителя n за время C\sqrt{λn}(Log n)³, не превосходит величины e^{- λ}.
