Entier friable

En théorie des nombres, un nombre friable, ou lisse, est un entier naturel dont l'ensemble des facteurs premiers sont petits, relativement à une borne donnée.

Les entiers friables sont particulièrement importants dans la cryptographie basée sur la factorisation, qui constitue depuis le début des années 2000 une branche dynamique de la théorie des nombres, avec des applications dans des domaines aussi variés que l'algorithmique (problème du logarithme discret), la théorie de la sommabilité (sommation friable des séries de Fourier), la théorie élémentaire des nombres premiers (preuve élémentaire du théorème des nombres premiers de Daboussi en 1984), la méthode du cercle (problème de Waring), le modèle de Billingsley, le modèle de Modèle:Lien, l'Modèle:Lien, les théorèmes de type Erdős-Wintner, etc.

Terminologie

Le terme Modèle:Langue (lisse) est proposé en anglais par le cryptologue américain Ronald Linn Rivest au début des années 1980. Le terme friable, qui désigne la capacité d'un objet à se réduire en menus fragments, est ensuite proposé par l'ingénieur polytechnicien Jacques Balazard, époux de l'écrivaine Simone Balazard et père du mathématicien Michel Balazard. Il s'impose peu à peu à toute la littérature en français et une partie de celle en anglais.

Définition

Un entier strictement positif est dit B-friable, ou B-lisse, si tous ses facteurs premiers sont inférieurs ou égaux à B.

Par exemple 72 900 000 000 = 2Modèle:8 × 3Modèle:6 × 5Modèle:8 est 5-friable car aucun de ses facteurs premiers ne dépasse 5.

Dans cette définition, B n'est pas nécessairement un facteur premier de l'entier B-friable : 12 est 5-friable, ou 5-lisse, même si 5 n'est pas un facteur de 12. Le nombre B n'a pas non plus besoin d'être premier.

Répartition

D'après Hildebrand-Tenenbaum, pour tout $\epsilon >0$, le nombre $\mathrm{\Psi }(x,y)$ des entiers y-friables n'excédant pas x vérifie

$(*)\mathrm{\Psi }(x,y)=x\varrho (u)\exp O(R)$

dès que $y>(\log x{)}^{1+\epsilon }$, où $u:=(\log x)/\log y$, et

$R:=(\log (u+1))/\log y+u\exp (-(\log y{)}^{3/5-\epsilon }).$

Cela implique notamment

$(**)\mathrm{\Psi }(x,y)=\{1+o(1)\}x\varrho (u)$

si $y>\exp (\log \log x{)}^{5/3+ϵ}$, où $\varrho$ désigne la fonction de Dickman.
De plus, Hildebrand a montré que la formule $\mathrm{\Psi }(x,y)=x\rho (u)\exp \{O(1)\}$ est valable dans le domaine

$y>(\log x{)}^{2+\epsilon }$

si et seulement si l'hypothèse de Riemann est vraie.

Entier ultrafriable

Un nombre est dit B-superlisse ou B-ultrafriable si tous ses diviseurs de la forme Modèle:Mvar, avec Modèle:Mvar premier et Modèle:Mvar entier, sont inférieurs ou égaux à B.

Par exemple, 720 (2Modèle:43Modèle:25Modèle:1) est 5-lisse mais pas 5-ultralisse (parce qu'il a des diviseurs primaires plus grands que 5 : 3Modèle:2 = 9 > 5 ou 2Modèle:3 > 5). Il est par contre 16-ultralisse puisque son plus grand diviseur primaire est 2Modèle:4 = 16. Ce nombre est bien sûr aussi 17-ultralisse, 18-ultralisse, etc.

Les nombres ultrafriables interviennent en algorithmique, en théorie des graphes et bien entendu en théorie des nombres.

Voir aussi

Bibliographie

• Modèle:Ouvrage
• Modèle:Ouvrage.
• Modèle:Article

Liens externes

Suites des nombres y-friables sur l'encyclopédie en ligne des suites de nombres entiers :

• nombres 2-friables : Modèle:OEIS2C (2ⁱ)
• nombres 3-friables : Modèle:OEIS2C (2ⁱ3^j)
• nombres 5-friables : Modèle:OEIS2C (2ⁱ3^j5^k)
• nombres 7-friables : Modèle:OEIS2C (2ⁱ3^j5^k7^l)
• nombres 11-friables : Modèle:OEIS2C
• nombres 13-friables : Modèle:OEIS2C
• nombres 17-friables : Modèle:OEIS2C
• nombres 19-friables : Modèle:OEIS2C
• nombres 23-friables : Modèle:OEIS2C

(etc.)