Ρ-алгоритм Полларда

Материал из Википедии — свободной энциклопедии

ρ-aлгоритм Дж. Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основан на том, что вычисляется некий многочлен степени не выше второй от начального числа Х — f(X).

[править] Описание алгоритма

Пусть надо разложить на множители число P

• Шаг 1. Выбирается многочлен f(x) с целочисленными коэффициентами, степени не выше 2. Обычно берется многочлен вида y = x² + c(mod P).
• Шаг 2. Случайно выбирается x₀ = y₀ меньше P.
• Шаг 2. Вычисляются значения x_i = f(x_{i − 1})(modP),y_i = f(f(y_{i − 1}))(modP).
• Шаг 3. Находится d = ( | x_i − y_i | ,P).
• Шаг 4. Если d = 1, происходит переход на шаг 2, если d = P, происходит остановка - факторизацию провести не удалось. Если 1 < d < P, то найдено разложение числа P.

[править] Альтернативное описание

• Шаг 1. Выбирается многочлен f(x) с целочисленными коэффициентами, степени не выше 2 и целое число m.
• Шаг 2. Случайно выбирается x₀ меньше P.
• Шаг 3. Вычисляются значения x_i = f(x_{i − 1})(modP).
• Шаг 4. Для h = 0,1,...,[logm] полагаем j = 2^h − 1 и для каждого 2^h < = k < 2^{h + 1} вычисляем d = ( | x_j − x_k | ,P). Если 1 < d < P, то нетривиальный делитель числа n найден. Если d=1 или d=P, то переходим к следующему значению h.

[править] Сложность алгоритма

Пусть n — составное число. Тогда существует такая константа C, что для любого положительного числа λ вероятность события, состоящего в том, что ρ-метод Полларда не найдет нетривиального делителя n за время , не превосходит величины e ^{− λ}. Метод Монте-Карло