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

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

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

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

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

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

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 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

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.