Уравнения Пелля без иррациональных чисел

[dmd]

Предлагаю к обсуждению статью Norman Wildberger "Pell’s equation without irrational numbers". Хотелось бы воспроизвести метод в pari/gp и проверить на составных $D$, что у меня пока не получается, т.к. не всё понимаю в статье. Самое интересное - равносильна вычислительная трудоёмкость факторизации составных $D$, или нет.

[iifat]

Пробежал глазами — вроде ж всё просто, не? Делаем вектор, подвергаем левым/правым преобразованиям в зависимости от, пока не получим исходный, ну и так далее. Что именно непонятно?

[dmd]

Проинтерпретировалось в коде так:

njw(d)=
{
 L= [1,0;1,1]; R= [1,1;0,1];
 A= [1,0;0,-d]; Q= A; N= 1;
 while(1,
  a= Q[1,1]; b= Q[1,2]; c= Q[2,2];
  t= a+2*b+c;
  if(t<0, Q= R~*Q*R; N= N*R, Q= L~*Q*L; N= N*L);
  if(Q==A, break())
 );
 return(N[,1]~)
};

Проверка:

? #
   timer = 1 (on)
?
? \r njw.gp
?
? njw(2)
%2 = [3, 2]
?
? njw(7)
%3 = [8, 3]
?
? njw(61)
%4 = [1766319049, 226153980]
?
? njw(991)
%5 = [379516400906811930638014896080, 12055735790331359447442538767]
?
? pell=njw(8616460799);
time = 1,357 ms.
?
? gcd(pell[1]-1,8616460799)
%7 = 96079
?
? factorint(8616460799)
%8 =
[89681 1]

[96079 1]

Кто-нибудь может прокомментировать пункт 8.Speeding up the algorithm, или что можно подкрутить, чтоб ускорить этот алгоритм?

[dmd]

На русском по теме от А.В. Спивак: видео и книжка "Арифметика-2" (Библиотечка Квант, с.75).
Моя реализация в Геогебре.