Algorithme PQa

Cet algorithme dû à Lagrange donne le développement en fraction continue d'un nombre quadratique (u+√D)/v, avec u, v, D entiers, D non carré.

D :     u :     v :          (u=0, v=1 pour résoudre x²-Dy²=±1)
Valeur des réduites     nombre de cycles supplémentaires

Fonctionnement

L'algorithme nécessite v divisant D-u².
Si v ne divise pas D-u², on peut remplacer u par u|v|, D par Dv² et v par v|v| et alors v|v| divise bien Dv²-u²v², tout en représentant le même nombre quadratique.

Posons U0=u, V0=v, a=E[√D], avec la notation E[x]=partie entière de x. Et les variables suplémentaires X, Y, P    X-1=-u, X0=v     Y-1=1, Y0=0     P-1=0, P0=1 Puis itérons les formules pour i≥0:     ai=E[(Ui+√D)/Vi]=E[(Ui+a)/Vi]     Ui+1=aiVi-Ui     Vi+1=(D-Ui+1²)/Vi,     (X,Y,P)i+1=ai(X,Y,P)i+(X,Y,P)i-1 En s'arrêtant quand la suite Vn devient périodique. Les ai sont les termes de la fraction continue,   Pi/Yi les réduites   et Xi²-DYi²=(-1)iV0Vi