| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Метод Р. Брента для факторизации |
| Автор: Reshetov 9.10.2009, 16:02 |
| Я нашел последовательность чисел для факторизации типа: 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 |