Validité de l'algorithme ~ L'algorithme AKS

Validité de l'algorithme

Une 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).

Plan de la démonstration de la validité de l'algorithme AKS

Notations

On définit les corps premiers finis et une structure d'anneau-quotient sur les polynômes. Des notations sont ensuite introduites pour l'ordre des éléments, l'indicateur d'Euler, la valuation p-adique et les parties entières par défaut et par excès.

Résultats liminaires

Un peu de dénombrement : des résultats de combinatoire ;

Le théorème d'Euler : l'ordre d'un élément divise φ(n) ;

L'introspection.

Résultats préliminaires

Minoration du ppcm : si n > 6, le plus petit commun multiple des n premiers entiers naturels non nuls est supérieur ou égal à 2ⁿ ;

Polynômes cyclotomiques : notions de base.

Démonstration de la validité de l'algorithme

Premier pas : si n est premier, l'algorithme retourne que n est premier ;

Encadrement de r < ⌈16log(n)⁵⌉ ;

Application de l'introspection ;

Encadrement de cardinaux de certains groupes ;

Théorème fondamental : l'algorithme retourne que n est premier si, et seulement si, n est premier.