C'est le nombre de chiffres du nouveau record de factorisation pour la
méthode ECM (Elliptic Curve Method).
Bruce Dodson,
chercheur de l'université de Lehigh (Pennsylvanie)
a en effet trouvé le 6 avril 2005 que :
À quoi ça sert ? Un tel record permet d'avoir une idée précise de l'efficacité pratique d'un algorithme comme ECM. L'objet mathématique utilisé par ECM, à savoir la courbe elliptique, est aussi à la base d'autres algorithmes, comme ECPP pour la preuve de primalité. C'est surtout une alternative à l'algorithme RSA pour la cryptographie, alternative qui est notamment valorisée par la société Certicom.
Pourquoi c'est difficile ? Le problème de la factorisation d'entier est en quelque sorte l'inverse de la multiplication. Multiplier 3 par 5 donne 15 ; la factorisation de 15 consiste à retrouver les deux facteurs 3 et 5. Il peut y avoir plus de deux facteurs comme 1001 = 7 * 11 * 13, ou bien un seul comme 1009 = 1009. On s'arrête quand tous les facteurs trouvés sont premiers, c'est-à-dire divisibles uniquement par 1 et eux-mêmes. Tester qu'un entier est premier est très efficace : il existe des algorithmes probabilistes très rapides, et d'autres déterministes comme fastECPP permettant de prouver la primalité d'entiers de plus de 15000 chiffres. La factorisation quant à elle reste un problème difficile. Le record pour les algorithmes dont la complexité ne dépend que de la taille du nombre à factoriser (comme MPQS ou GNFS) est de 176 chiffres.La barrière des 60 chiffres. Ce nouveau record pour la méthode ECM de factorisation via les courbes elliptiques pulvérise la barrière psychologique des 60 chiffres décimaux. La barrière des 50 chiffres a quant à elle été franchie en 1998, avec un record de 53 chiffres trouvé par Conrad Curry. Richard Brent maintient un historique des records ECM, et des 10 plus grands facteurs trouvés à ce jour.
Un bond prodigieux en avant. Ce nouveau record bat le précédent (59 chiffres, trouvé aussi par Bruce Dodson en février 2005) de 7 chiffres. Un tel bond en avant est une première dans l'histoire des records ECM. En effet, on est passé de 40 chiffres en 1991 à 42 chiffres en 1992, puis à 43 en 1993, 44 puis 47 en 1995, 48 en 1997, 49 et 53 en 1998, 54 en 1999, 55 en 2002, 57 en 2003, 59 et 66 en 2005.
L'algorithme ECM. Inventé par Hendrik W. Lenstra, Jr. en 1985, ECM (pour Elliptic Curve Method en anglais) est le meilleur algorithme connu, parmi ceux dont la complexité ne dépend essentiellement que de la taille du facteur trouvé --- ici de 66 chiffres --- et non du nombre à factoriser --- ici de 180 chiffres. Pour la petite histoire, lorsque ECM a été inventé, certains chercheurs ont prédit que cet algorithme ne trouverait jamais un facteur de plus de 30 chiffres !
Détails techniques. Le facteur de 66 chiffres de 3466+1 a été trouvé à l'aide du programme GMP-ECM développé par Jim Fougeron, Laurent Fousse, Alexander Kruppa, Dave Newman et Paul Zimmermann. La courbe elliptique qui a trouvé ce facteur utilise sigma=1875377824 selon la paramétrisation de Suyama. L'ordre du groupe correspondant est