## [Test de Lissité](/fr/node/62929) Définition Le processus consistant à déterminer si un entier n est B‑lisse, c’est‑à‑dire si tous ses facteurs premiers sont ≤ B, généralement en tentant la factorisation jusqu’à la borne B ou en appliquant des tests spécialisés de lissité. ## Principe Principe Commencer par la division par essais par tous les premiers ≤ B, combinée au criblage et à des techniques de factorisation partielles (Pollard rho, p−1, ECM) pour détecter les cofactors restants ; certifier la lissité seulement lorsque la factorisation complète montre des premiers ≤ B. ## Démonstration Démonstration Exemple : n = 360 = 2^3·3^2·5 est 5‑lisse car son plus grand facteur premier est 5 ; en revanche 1001 = 7·11·13 n’est pas 5‑lisse car il contient des premiers >5. ## Mauvaise application Mauvaise application Confondre la présence de nombreux petits facteurs avec la B‑lissité, ou arrêter la division par essais trop tôt et déclarer la lissité alors qu’un grand facteur premier non découvert subsiste ; utiliser des heuristiques probabilistes comme preuve sans vérification est aussi erroné. ## Conséquence Conséquence La détection de la lissité est cruciale pour les stratégies de factorisation (ECM, crible quadratique), les attaques cryptanalytiques exploitant des ordres lisses et pour les analyses de complexité où des entrées lisses permettent des algorithmes plus rapides. ## Inversion Inversion Le problème opposé est la détection de rugosité : prouver l’existence d’un facteur premier >B peut parfois être plus simple (trouver un seul grand premier) et constitue l’affirmation négative à la lissité. ## Limite Limite S’applique aux entiers positifs et à une borne explicite B≥2 ; nécessite la factorisation complète jusqu’à B pour certifier la lissité ; exclut les structures multiplicatives sur des anneaux où la notion de primalité diffère (par ex. domaines de non‑factorisation unique) sauf si l’on interprète correctement les « premiers ». ## Tension sémantique Tension sémantique Tension entre le dépistage pratique heuristique (tests probabilistes rapides ou criblage partiel) et la certification rigoureuse (factorisation complète), et entre l’abondance de petits facteurs et le facteur premier unique qui rompt la lissité. ## Synthèse Synthèse Le test de lissité est la tâche procédurale visant à vérifier que chaque diviseur premier d’un entier est inférieur à un seuil donné B, réalisée par une chaîne de divisions par essais, criblage et méthodes de factorisation ciblées, et servant de prédicat clé en algorithmique des nombres et en cryptanalyse.