Conclusion

Document PDF à téléchargerUne partie seulement de cet exposé est présent sur le site. La version complète, qui comprend la démonstration intégrale de la validité de l'algorithme AKS, n'est disponible que dans le fichier rédigé à l'aide d'AMS-LaTeX, téléchargeable dans une version PDF PDF pour en faciliter la consultation et l'impression.
Une version allégée de cet exposé est aussi parue dans le soixantième numéro du magazine de mathématiques pures et épicées Quadrature (avril–juin 2006, édité par EDP Sciences).
 

Applications de l'algorithme AKS

À l'heure actuelle, il n'existe aucune application réalisable de l'algorithme, indique Agrawal lui-même : ce dernier préfère considérer le problème comme un « défi intellectuel »

Interrogé sur le dépôt d'un éventuel brevet sur l'algorithme, Agrawal se montre d'ailleurs catégoriquement opposé, bien que l'Institut Indien de Technologie eût voulu la protection de l'algorithme.

On peut en conséquence raisonnablement penser que l'algorithme sera efficacement amélioré dans les prochaines années par les mathématiciens. Il suffit en effet de constater la grande différence qui existe entre les deux versions de l'algorithme AKS : en août 2002, sa complexité temporelle est en Ω(log(n)12) et la démonstration requiert de puissants outils d'analyse et d'algèbre, tandis qu'en mars 2003, elle est en Ω(log(n)10.5) et la démonstration devient somme toute assez élémentaire dans les moyens usités.

De nombreux mathématiciens et théoriciens se sont en effet penchés sur le problème et ont contribué à l'amélioration de l'algorithme dont de nombreuses variantes ont été trouvées. Dan Bernstein s'est par exemple inspiré de l'idée de l'algorithme pour en réaliser un en Ω(log(n)4), mais non déterministe ; il annonce ainsi la résolution d'un nombre de 300 chiffres en un jour avec une implémentation utilisant la librairie GMP pour manipuler des grands nombres sur un Pentium-III de 800 MHz.

L'informatique fera aussi des progrès et les ordinateurs seront à même d'exécuter plus rapidement l'algorithme : une différence en rapidité qui va du simple au quintuple est notable pour seulement 300 MHz supplémentaires.

Il est même possible que l'algorithme excelle sur les tests de primarité qui sont actuellement utilisés, notamment dans le domaine de la cryptographie, lorsque de très grands nombres premiers sont nécessaires et qu'aucune erreur ne peut être tolérée sur leur primarité.

P est un problème de classe P

Il résulte ainsi que l'algorithme AKS se révèle trop lent pour le moment en l'état ; mais nul doute qu'une variante lui permettra de rivaliser avec les algorithmes actuels, à moins que l'une des conjectures énoncées lors de l'étude de sa complexité ne soit démontrée, ce qui conduirait à une complexité temporelle en Ω(log(n)3) dans le meilleur des cas.

Certes l'algorithme demeure de nos jours inutilisable en pratique à grande échelle ; cela n'assombrit cependant en rien la beauté du résultat théorique établi par les auteurs de l'algorithme, à savoir que la détermination de la primarité d'un nombre est un problème de classe P, et qui suscite l'émerveillement de toute la communauté mathématique.

À la lueur de la démonstration de cet algorithme, on peut par ailleurs légitimement se demander si d'autres résultats mathématiques dont la démonstration nous échappe encore, ne posséderaient pas une preuve aussi « brillante, élégante et simple » que celle-ci.

 

↑ Retour au haut de cette page

Pages connexes

← Retour au menu précédent