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 une vingtaine d'années 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^[1]), la théorie élémentaire des nombres premiers (preuve élémentaire du théorème des nombres premiers de Daboussi en 1984^[2]), la méthode du cercle (problème de Waring), le modèle de Billingsley, le modèle de Kubilius (en), l'inégalité de Turán-Kubilius (en), les théorèmes de type Erdős-Wintner, etc.

Terminologie[modifier | modifier le code]

Le terme smooth (lisse) est proposé en anglais par le cryptologue américain Ronald Linn Rivest au début des années 1980^[3]. 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^[4].

Définition[modifier | modifier le code]

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 = 2⁸ × 3⁶ × 5⁸ 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[modifier | modifier le code]

D'après Hildebrand-Tenenbaum^[5], pour tout $\varepsilon >0$ , le nombre $\Psi (x,y)$ des entiers y-friables n'excédant pas x vérifie

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

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

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

Cela implique notamment

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

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

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

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

Entier ultrafriable[modifier | modifier le code]

Un nombre est dit B-superlisse ou B-ultrafriable si tous ses diviseurs de la forme $p n$ , avec $p$ premier et $n$ entier, sont inférieurs ou égaux à B.

Par exemple, 720 (2⁴3²5¹) est 5-lisse mais pas 5-ultralisse (parce qu'il a des diviseurs primaires plus grands que 5 : 3² = 9 > 5 ou 2³ > 5). Il est par contre 16-ultralisse puisque son plus grand diviseur primaire est 2⁴ = 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.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Smooth number » (voir la liste des auteurs).

↑ R. de la Bretèche et G. Tenenbaum, « Séries trigonométriques à coefficients arithmétiques », Journal d'Analyse Mathématique (nl), vol. 92,‎ 2004, p. 1-79.
↑ Cf. Tenenbaum et Mendès France 2013.
↑ « J'ai inventé le terme de "nombre lisse" pour désigner un nombre qui n'a que des petits facteurs premiers. Je ne me rappelle pas bien comment j'y ai pensé, sinon que "lisse" est plutôt le contraire de "grumeleux". » (Ronald Rivest, cité dans une discussion MathOverflow mentionnée dans Tenenbaum, Des mots et des maths).
↑ Gérald Tenenbaum, Des mots et des maths, Paris, Odile Jacob, 2019, 215 p. (ISBN 978-2-7381-4900-8), p. 80-81
↑ (en) A. Hildebrand et G. Tenenbaum, « On integers free of large prime factors », Trans. Amer. Math. Soc., vol. 296,‎ 1986, p. 265-290 (voir aussi Tenenbaum 2015).
↑ (en) A. Hildebrand, « Integers free of large prime factors and the Riemann hypothesis », Mathematika, vol. 31,‎ 1984, p. 258-271.

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

nombre lisse, sur le Wiktionnaire

Bibliographie[modifier | modifier le code]

Gérald Tenenbaum et Michel Mendès France, Les nombres premiers, entre l'ordre et le chaos, Dunod, 2013 (ISBN 978-2-10-070656-3 et 2-10-070656-X)
Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Paris, Belin, 2015, 592 p. (ISBN 978-2-7011-9656-5).
Jean-Paul Delahaye, « Les entiers friables », Pour la science, n^o 539,‎ septembre 2022, p. 80-85

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

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

nombres 2-friables : A000079 (2ⁱ)
nombres 3-friables : A003586 (2ⁱ3^j)
nombres 5-friables : A051037 (2ⁱ3^j5^k)
nombres 7-friables : A002473 (2ⁱ3^j5^k7^l)
nombres 11-friables : A051038
nombres 13-friables : A080197
nombres 17-friables : A080681
nombres 19-friables : A080682
nombres 23-friables : A080683

(etc.)

Arithmétique et théorie des nombres

[1] R. de la Bretèche et G. Tenenbaum, « Séries trigonométriques à coefficients arithmétiques », Journal d'Analyse Mathématique (nl), vol. 92,‎ 2004, p. 1-79.

[2] Cf. Tenenbaum et Mendès France 2013.

[3] « J'ai inventé le terme de "nombre lisse" pour désigner un nombre qui n'a que des petits facteurs premiers. Je ne me rappelle pas bien comment j'y ai pensé, sinon que "lisse" est plutôt le contraire de "grumeleux". » (Ronald Rivest, cité dans une discussion MathOverflow mentionnée dans Tenenbaum, Des mots et des maths).

[4] Gérald Tenenbaum, Des mots et des maths, Paris, Odile Jacob, 2019, 215 p. (ISBN 978-2-7381-4900-8), p. 80-81

[5] (en) A. Hildebrand et G. Tenenbaum, « On integers free of large prime factors », Trans. Amer. Math. Soc., vol. 296,‎ 1986, p. 265-290 (voir aussi Tenenbaum 2015).

[6] (en) A. Hildebrand, « Integers free of large prime factors and the Riemann hypothesis », Mathematika, vol. 31,‎ 1984, p. 258-271.

[1]

[2]

[3]

[4]

[5]

[6]

v · m Ensembles d'entiers sur la base de leur divisibilité
Formes de factorisation	Nombre premier Nombre composé Nombre puissant Entier sans facteur carré
Sommes de diviseurs	Nombre parfait Nombre presque parfait Nombre quasi parfait Nombre parfait multiple Nombre hémiparfait Nombre hyperparfait Nombre superparfait Nombre unitairement parfait Nombre semi-parfait Nombre semi-parfait primitif Nombre pratique Nombre abondant Nombre hautement abondant Nombre superabondant Nombre colossalement abondant Nombre déficient Nombre étrange Nombre intouchable
Nombreux diviseurs	Nombre hautement composé Nombre hautement composé supérieur
Autre	Nombres amicaux Nombre sociable Nombre solitaire Nombre sublime Nombre à moyenne harmonique entière Nombre frugal Nombre équidigital Nombre extravagant