Розклад числа на прості множники, Детальна інформація

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

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

1. a =\xF0202, b =\xF0202;

2. for i \xF0AC\xF0201 to t do

2.1. Обчислити a \xF0AC\xF020\xF028a2 + 1) mod n; b \xF0AC\xF020\xF028b2 + 1) mod n; b \xF0AC\xF020\xF028b2 + 1) mod n;

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

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

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

) операцій модулярного множення.

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

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

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

a b d

2 2 1

5 26 1

26 19672 1

677 12391 1

19672 15217 1

11473 15217 1

12391 15217 157



Знайдено розклад 19939 = 157 * 127.

Нехай n = 143. Послідовність xi: 2, 5, 26, 105, 15, ... .

a b d

2 2 1

5 26 НСД(21, 143) = 1

26 15 НСД(11, 143) = 11



Знайдено розклад 143 = 11 * 13.

Ймовірносний квадратичний алгоритм факторизації числа