Факторизация Бриллхарта-Моррисона (вопрос по цепным дробям)

[lonelyass]

Прошу помочь людей, имевших дело с этим методом. Сразу оговорюсь, что он у меня работает, числа раскладывает, но я не понимаю, адекватно ли происходящее в процессе.

В алгоритме Бриллхарта-Моррисона получение пар A, Q для которых выполняется $Q = A^2 mod N$ происходит через разложение в цепную дробь числа $\sqrt N$. Мало знакомый с цепными дробями, я долго искал подробный алгоритм генерации. В результате наткнулся на оригинальную работу Померанса - Implementation of the continued fraction integer factoring algorithm, где на 4ой странице есть подробное описание следующего вида:
$Q_n = Q_{n-2} + q_{n-1}*(r_{n-1} - r_{n-2})$
$G_n = 2*g - r_{n-1}$
$q_n = [G_n/Q_n]$
$r_n = G(n) - q(n)*Q(n)$
$A_n = (q_n*A_{n-1} + A_{n-2}) mod N$

$g = \sqrt N$
$Q_{-1} = N$
$Q_0 = 1$
$q_0 = g$
$r_{-1} = g$
$r_0 = 0$
$A_{-1} = 1$
$A_0 = g$

В общем я реализовал эту последовательность, но почему-то пары генерируются через шаг.
Тоесть не для каждого шага получается пара, а для каждых двух соседних шагов.
Чтобы объяснить понятнее, даю отрывок из файла с парами:
N = 3217104339627144632956527751747 (102 bits)
An^2 mod N = 1522905984030422 # Qn = 2064351653568051
An^2 mod N = 3217104339627143550065188676488 # Qn = 1522905984030422
An^2 mod N = 2200073224775814 # Qn = 1082891339075259
An^2 mod N = 3217104339627143922939355674480 # Qn = 2200073224775814
An^2 mod N = 1131588038634766 # Qn = 710017172077267
An^2 mod N = 3217104339627142234911540524884 # Qn = 1131588038634766
В результате я, конечно, просто отбираю пары по диагонали и всё работает. Но я не могу понять: так должно быть или я накосячил в реализации последовательности? Если второе, то после исправления количество шагов станет вдвое меньше.

[maxal]

lonelyass в сообщении #318095 писал(а):

N = 3217104339627144632956527751747 (102 bits)
An^2 mod N = 1522905984030422 # Qn = 2064351653568051
An^2 mod N = 3217104339627143550065188676488 # Qn = 1522905984030422
An^2 mod N = 2200073224775814 # Qn = 1082891339075259

Тут просто-напросто знак скачет - заметьте, что

$$3217104339627143550065188676488 \equiv -1082891339075259\pmod{N}$$

-- Tue May 11, 2010 23:32:04 --

Кстати, описание метода факторизации с помощью цепных дробей на русском есть в
http://www.mathnet.ru/rus/intf147 стр. 79-80 и около

[lonelyass]

Огромное спасибо, сам не заметил
В принципе, тему можно закрывать.

[moska625]

скиньте реализацию алгоритма на с++ пожалуйста

[Deggial]

moska625, замечание за капслок.
Капслок убран.