Nombres k-friables et k-résistants; Sayrac 2023

NOMBRES k-FRIABLES et NOMBRES k-RESISTANTS

(en construction, 18 janvier 2023)

Dans le cadre de la factorisation des entiers, avec en particulier de grandes applications en cryptographie, la notion de nombre friable est devenue utile et importante depuis quelques décennies et de nombreux auteurs ont établi diverses propriétés (en particulier Erdös, Hamming, Ramanujan, ...).
De manière générale un nombre friable ou lisse (smooth number) est un entier dont tous les facteurs premiers sont petits, relativement à une borne donnée, c'est-à-dire encore un entier sans grand facteur premier.
Plus précisément, k étant un entier positif au moins égal à 2, un entier sera dit k-friable si tous ses facteurs premiers sont inférieurs ou égaux à k et un entier sera dit k-résistant si tous ses facteurs premiers sont strictement supérieurs à k.
Par exemple les nombres 2-friables sont 1 et les puissances de 2 (1, 2, 4, 8, ...), les nombres 3-friables sont les nombres en 2^p.3^q, p et q entiers positifs ou nuls (1, 2, 3, 4, 6, 8, 9, ...).
Ces nombres 3-friables sont particulièrement intéressants en rapport avec le théorème de Erdös et Lewin (1996) qui montre que tout entier s'exprime comme une somme finie de nombres 3-friables, aucun terme n'en divisant un autre.
Les nombres 5-friables sont encore appelés nombres réguliers ou nombres de Hamming et sont de la forme 2^p.3^q.5^r (p, q, r entiers positifs ou nuls)...
Dans la définition, k n'est pas nécessairement un facteur premier de l'entier k-friable et n'est pas nécessairement un nombre premier, mais dans la pratique on préfèrera utiliser des k premiers. De manière générale on dira:
Définition. n est k-friable (k premier) si n = 2^a.3^b.5^c...k^z, avec a, b, c, ...z entiers positifs ou nuls (z>0).
Naturellement si un entier n est k-friable il est aussi (trivialement) k*-friable pour tout entier k* > k.
Si on note un entier n = p₁^a.p₂^b...p_r^z, les p_i, i = 1, 2, ..., r, étant ses facteurs premiers (à une puissance >0), on pourra appeler P le plus grand et p le plus petit; on dira alors:
n est k-friable si P <= k et n est k-résistant si p > k.
Par exemple, un nombre 3-résistant est de la forme n = 5^a.7^b.11^c...., a, b, c, ...étant non tous nuls (a>0 sinon n serait 5-résistant).
Naturellement si un entier n est k-résistant il est aussi (trivialement) k*- résistant pour tout entier k* < k.
Ces entiers jouent un rôle important en cryptographie où la factorisation est capitale ...en particulier pour les entiers N produits de deux grands nombres premiers p, q (d'au moins une centaine de chiffres), nombres k-résistants bipremiers avec k suffisamment grand (largement utilisés dans les techniques de l' algorithme RSA ). La sécurité de tels algorithmes repose sur l'énorme difficulté actuelle (pour ne pas dire impossibilité !) pour factoriser de tels N=pq (et donc obtenir p et q à partir de la seule connaissance de N); la factorisation 'manuelle' d'un nombre d'une dizaine de chiffres peut déjà être difficile (par exemple 2435209979=48889.49811 ou 175849723097207=3216233.54675679).
On conviendra de parler de k-friable pour un entier dont le plus grand diviseur premier est k (à une puissance z>0), et de k-résistant pour un entier dont le plus petit diviseur premier est le nombre premier k₊ (à une puissance a>0) immédiatement strictement supérieur à k.
En notant p_i, i = 1, 2, ..., r, les facteurs premiers classés de manière strictement croissante d'un entier n, un entier k-friable sera n = p₁^a.p₂^b...p_r-1^y.k^z (z>0); un entier k-résistant sera n = k₊^a.p₂^b.p₃^c...p_r^z... (a>0), k₊ étant le premier immédiatement strictement supérieur à k.
Exemple comparatif (entiers de l'ordre de 10¹⁰):
10000000019 est premier,
10000000000 = 2¹⁰.5¹⁰ est 5-friable (très facile à factoriser),
10000841621 = 99607.100403 est 99606-résistant (bipremier plus difficile à factoriser).
On observera que parmi tous les k-friables, il n'y a jamais de nombre premier autre que 2, mais il y a toutes les puissances de 2, et que parmi tous les k-résistants, il n'y a jamais de nombre pair mais il y a tous les premiers strictement supérieurs à k.

Etant donnés un entier n et un entier k, le petit code suivant répondra aux questions, n est-il k-friable, n est-il k-résistant; il donnera par ailleurs le plus petit k de friabilité, le plus grand k de résistance et la factorisation de n. Deux autres boutons donneront, pour le k choisi, des listes de nombres k-friables ou de nombres k-résistants. Le quatrième bouton donnera des nombres bipremiers k-résistants; un cinquième bouton donnera des nombres bipremiers k-résistants se terminant par 3 ou 7, ce qui interdira les carrés parfaits. Le tout dernier bouton donnera tous les nombres bipremiers entre 10000 et 50000.
Ici vous n'avez droit qu'à 20 secondes de calcul ...Aller vers la version BIWI (60 secondes de calcul) )