Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Entier friable
Résumé
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), 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 , l', les théorèmes de type Erdős-Wintner, etc.
Le terme smooth (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.
Un entier strictement positif est dit B-friable, ou B-lisse, si tous ses facteurs premiers sont inférieurs ou égaux à B.
Par exemple = 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.
D'après Hildebrand-Tenenbaum, pour tout , le nombre des entiers y-friables n'excédant pas x vérifie
dès que ,
où
et
Cela implique notamment
si , où désigne la fonction de Dickman.
De plus, Hildebrand a montré que la formule est valable dans le domaine
si et seulement si l'hypothèse de Riemann est vraie.
Un nombre est dit B-superlisse ou B-ultrafriable si tous ses diviseurs de la forme p, avec p premier et n entier, sont inférieurs ou égaux à B.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (3)
MATH-489: Number theory II.c - Cryptography
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
MATH-482: Number theory I.a - Algebraic number theory
Algebraic number theory is the study of the properties of solutions of polynomial equations with integral coefficients; Starting with concrete problems, we then introduce more general notions like alg
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how