Розклад числа на прості множники

Тоді послідовність xi має вигляд: 1, 4, 19, 7, 10, 19, 7, 10, ... .

Таким чином x3 = x6, період послідовності дорівнює 3.

Послідовність xi можна відобразити у вигляді кола з хвостом: коло відповідає періодичній частині, а хвіст – доперіодичній. Картинка нагадує грецьку літеру , тому метод який застосовується в алгоритмі називається  – евристикою. Послідовність із попереднього прикладу можна зобразити так:

Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d = НСД(x2i – xi, n). Якщо на деякому кроці d > 1, то це і є нетривіальний дільник числа n.

Побудуємо послідовність елементів xi наступним чином:

x0 = 2, xi+1 = f(xi) = ( + 1) mod n, i > 0

Алгоритм

Вхід: натуральне число n, параметр t 1.

Вихід: нетривіальний дільник d числа n.

1. a =2, b =2;

2. for i 1 to t do

2.1. Обчислити a a2 + 1) mod n; b b2 + 1) mod n; b b2 + 1) mod n;

2.2. Обчислити d НСД(a - b, n);

2.3. if 1 < d < n return (d); // знайдено нетривіальний дільник

3. return (False);// дільника не знайдено

Вважаємо, що функція f(x) = (x2 + 1) mod n генерує випадкові числа. Тоді для знаходження дільника числа n необхідно виконати не більш ніж O( ) операцій модулярного множення.

Якщо алгоритм Поларда – ро не знаходить дільника за t ітерацій, то замість функції f(x) = (x2 + 1) mod n можна використовувати f(x) = (x2 + c) mod n, для деякого цілого c, c 0, -2.

Приклад. Нехай n = 19939.

Послідовність xi: 2, 5, 26, 677, 19672, 11473, 12391, 6582, 15217, 5483, 15217, 5483, 15217, ... .

abd

221

5261

26196721