Bien sur que ça date, n'empeche que ça reste la meilleure réference pour les applications pratiques. De toute les façons toutes les améliorations sont déduites de J. Stein, et la complexité théorique reste quadratique en le longueur des opérandes.fakbill a écrit :Ca date un peu comme référence. Volume 2, Seminumerical Algorithms (troisième édition 1997).
A l'époque le test de primalité n'était pas P.
Dans mathematica, ils font ça:
"GCD interleaves the HGCD algorithm, the Jebelean\[Dash]Sorenson\[Dash]Weber accelerated GCD algorithm, and a combination of Euclid's algorithm and an algorithm based on iterative removal of powers of 2."
Je ne connais pas la version de Jebelean, et je t'en dirai plus si j'arrive à me la procurer. De toute façon si tu as d'autres références, je suis preneur.
Le test de Primalité n'etait pas P, à l'epoque, mais dans la pratique, pour des raisons de performance on continue toujours avec les méthodes probabilistes qui fournissent un bon résultat tant que la conjecture de Riemman n'est pas infirmée. Mais sûr que le trio a fait avancer les choses dans ce domaine.