Я нашел последовательность чисел для факторизации типа: x1 = f(x0), которая зацикливается, как и в методе rho Дж.Полларда.

Естественно, что применил к ней метод Р. Брента, чтобы ускорить поиск в цикле.  Но, как выяснилось, метод Брента не шибко надежный.

Привожу пример последовательности:

p = 151
q = 191
n = 28841
28, 87
55, 28
66, 28
50, 66
47, 66
92, 66
28, 66
55, 28
66, 28
50, 28
47, 28
92, 28
28, 28
Factor = 151, Steps = 13

Здесь, p и q - делители числа n


Далее идет последовательность чисел. Через запятую указаны остатки от деления на число p. Первое число до запятой - остаток деления очередного члена последовательности от деления на p. Второе число - находится по методу Брента (тоже представлен его остаток от деления на p), т.е. копирование первого числа через удвоенные промежутки.

Factor - результат факторизации

Steps - количество шагов факторизации


Но четко видно, что сама последовательность зацикливается гораздо раньше, нежели метод Брента успевает его перенести во вторую колонку.

Нельзя ли как нибудь усовершенствовать метод Брента, чтобы он обнаруживал зацикливание по мере его появления, без задержки?

Вот еще один пример:

p = 163
q = 199
n = 32437
118, 122
89, 118
100, 118
56, 100
24, 100
58, 100
162, 100
161, 162
79, 162
46, 162
85, 162
62, 162
133, 162
8, 162
110, 162
70, 110
77, 110
113, 110
38, 110
8, 110
110, 110
Factor = 163, Steps = 21