Factorisation d'entiers

En mathématiques , la factorisation d'entiers est la décomposition d'un entier positif en un produit d'entiers. Tout entier positif supérieur à 1 est soit le produit de deux ou plusieurs facteurs entiers supérieurs à 1, auquel cas il est appelé nombre composé , soit il ne l'est pas, auquel cas il est appelé nombre premier . Par exemple, 15 est un nombre composé car 15 = 3 · 5 , mais 7 est un nombre premier car il ne peut pas être décomposé de cette façon. Si l'un des facteurs est composé, il peut à son tour s'écrire comme un produit de facteurs plus petits, par exemple 60 = 3 · 20 = 3 · (5 · 4) . Continuer ce processus jusqu'à ce que tous les facteurs soient premiers est appelé factorisation première ; le résultat est toujours unique jusqu'à l'ordre des facteurs par le théorème de factorisation première .

Pour factoriser un petit entier n en utilisant le calcul mental ou sur papier, la méthode la plus simple est la division par essai : vérifier si le nombre est divisible par les nombres premiers 2 , 3 , 5 , etc., jusqu'à la racine carrée de n . Pour les nombres plus grands, en particulier lorsqu'on utilise un ordinateur, divers algorithmes de factorisation plus sophistiqués sont plus efficaces. Un algorithme de factorisation en nombres premiers consiste généralement à tester si chaque facteur est premier à chaque fois qu'un facteur est trouvé.

Lorsque les nombres sont suffisamment grands, aucun algorithme de factorisation d'entiers non quantique efficace n'est connu. Cependant, il n'a pas été prouvé qu'un tel algorithme n'existe pas. La difficulté présumée de ce problème est importante pour les algorithmes utilisés en cryptographie tels que le chiffrement à clé publique RSA et la signature numérique RSA . De nombreux domaines des mathématiques et de l'informatique ont été amenés à traiter ce problème, notamment les courbes elliptiques , la théorie algébrique des nombres et l'informatique quantique .

Tous les nombres d'une longueur donnée ne sont pas aussi difficiles à factoriser. Les exemples les plus difficiles de ces problèmes (pour les techniques actuellement connues) sont les nombres semi-premiers , le produit de deux nombres premiers. Lorsqu'ils sont tous deux grands, par exemple plus de deux mille bits de long, choisis au hasard et de taille à peu près identique (mais pas trop proche, par exemple, pour éviter une factorisation efficace par la méthode de factorisation de Fermat ), même les algorithmes de factorisation premiers les plus rapides sur les ordinateurs les plus rapides peuvent prendre suffisamment de temps pour rendre la recherche impraticable ; c'est-à-dire qu'à mesure que le nombre de chiffres de l'entier à factoriser augmente, le nombre d'opérations requises pour effectuer la factorisation sur n'importe quel ordinateur augmente considérablement.

De nombreux protocoles cryptographiques reposent sur la difficulté de factoriser de grands entiers composites ou sur un problème connexe, par exemple le problème RSA . Un algorithme capable de factoriser efficacement un entier arbitraire rendrait la cryptographie à clé publique basée sur RSA peu sûre.

D'après le théorème fondamental de l'arithmétique , chaque entier positif possède une factorisation première unique . (Par convention, 1 est le produit vide .) Le test de primalité d'un entier peut être effectué en temps polynomial , par exemple à l'aide du test de primalité AKS . Cependant, s'il s'agit d'un nombre composite, les tests en temps polynomial ne donnent aucune indication sur la manière d'obtenir les facteurs.

Étant donné un algorithme général de factorisation d'entiers, tout entier peut être factorisé en ses facteurs premiers constitutifs par application répétée de cet algorithme. La situation est plus compliquée avec les algorithmes de factorisation à usage spécifique, dont les avantages peuvent ne pas être aussi bien exploités, voire pas du tout, avec les facteurs produits lors de la décomposition. Par exemple, si n = 171 × p × q où p < q sont des nombres premiers très grands, une division par essai produira rapidement les facteurs 3 et 19, mais nécessitera p divisions pour trouver le facteur suivant. À titre d'exemple contrasté, si n est le produit des nombres premiers 13729 , 1372933 et 18848997161 , où 13729 × 1372933 = 18848997157 , la méthode de factorisation de Fermat commencera par ⌈ √ n ⌉ = 18848997159 qui donne immédiatement b = √ a ² − n = √ 4 = 2 et donc les facteurs a − b = 18848997157 et a + b = 18848997161 . Bien que ceux-ci soient facilement reconnus comme composés et premiers respectivement, la méthode de Fermat prendra beaucoup plus de temps pour factoriser le nombre composé car la valeur de départ de ⌈ √ 18848997157 ⌉ = 137292 pour a est un facteur de 10 à partir de 1372933 .

Parmi les nombres à b bits, les plus difficiles à factoriser en pratique à l'aide des algorithmes existants sont les nombres semi-premiers dont les facteurs sont de taille similaire. C'est pour cette raison que ce sont les entiers utilisés dans les applications cryptographiques.

En 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé et Paul Zimmermann ont factorisé un nombre de 240 chiffres (795 bits) ( RSA-240 ) en utilisant environ 900 années-cœurs de puissance de calcul. Les chercheurs ont estimé qu'un module RSA de 1024 bits prendrait environ 500 fois plus de temps.

Le plus grand nombre semi-premier factorisé à ce jour était RSA-250 , un nombre de 829 bits avec 250 chiffres décimaux, en février 2020. Le temps de calcul total était d'environ 2700 années-cœurs de calcul avec Intel Xeon Gold 6130 à 2,1 GHz. Comme tous les records de factorisation récents, cette factorisation a été réalisée avec une implémentation hautement optimisée du crible de champs numériques généraux exécuté sur des centaines de machines.

Aucun algorithme n'a été publié qui puisse factoriser tous les entiers en temps polynomial , c'est-à-dire qui puisse factoriser un nombre n à b bits en temps O ( bk ) pour une certaine constante k . Ni l'existence ni la non-existence de tels algorithmes ^n'ont été prouvées, mais on soupçonne généralement qu'ils n'existent pas.

Il existe des algorithmes publiés qui sont plus rapides que O((1 + ε ) ^b ) pour tout ε positif , c'est-à-dire sous-exponentiel . En 2022 , l'algorithme avec le meilleur temps d'exécution asymptotique théorique est le crible général de corps de nombres (GNFS), publié pour la première fois en 1993, exécuté sur un nombre n de b bits dans le temps :

Pour les ordinateurs actuels, GNFS est le meilleur algorithme publié pour les grands n (plus de 400 bits environ). Pour un ordinateur quantique , cependant, Peter Shor a découvert en 1994 un algorithme qui le résout en temps polynomial. ^L' algorithme de Shor ne prend que O( b3 ) temps et O( b ) espace sur des entrées de nombre b bits. En 2001, l'algorithme de Shor a été implémenté pour la première fois, en utilisant des techniques de RMN sur des molécules qui fournissent sept qubits.

Afin de parler de classes de complexité telles que P, NP et co-NP, le problème doit être énoncé comme un problème de décision .

On sait qu'il est à la fois NP et co-NP , ce qui signifie que les réponses « oui » et « non » peuvent être vérifiées en temps polynomial. Une réponse « oui » peut être certifiée en présentant une factorisation n = d ( ⁠n/d⁠ ) ​​avec d ≤ k . Une réponse « non » peut être certifiée en montrant la factorisation de n en nombres premiers distincts, tous plus grands que k ; on peut vérifier leur primalité en utilisant le test de primalité AKS , puis les multiplier pour obtenir n . Le théorème fondamental de l'arithmétique garantit qu'il n'y a qu'une seule chaîne possible de nombres premiers croissants qui sera acceptée, ce qui montre que le problème est à la fois en UP et en co-UP. On sait qu'il est en BQP en raison de l'algorithme de Shor.

On suppose que le problème se situe en dehors des trois classes de complexité P, NP-complet, et co-NP-complet . Il est donc candidat à la classe de complexité NP-intermédiaire .

En revanche, le problème de décision « n est-il un nombre composé ? » (ou de manière équivalente : « n est-il un nombre premier ? ») semble être beaucoup plus simple que le problème de spécification des facteurs de n . Le problème composé/premier peut être résolu en temps polynomial (dans le nombre b de chiffres de n ) avec le test de primalité AKS . De plus, il existe plusieurs algorithmes probabilistes qui peuvent tester la primalité très rapidement en pratique si l'on est prêt à accepter une possibilité d'erreur infinitésimale. La facilité du test de primalité est un élément crucial de l' algorithme RSA , car il est nécessaire de trouver de grands nombres premiers pour commencer.

Le temps d'exécution d'un algorithme de factorisation à usage spécifique dépend des propriétés du nombre à factoriser ou de l'un de ses facteurs inconnus : taille, forme spéciale, etc. Les paramètres qui déterminent le temps d'exécution varient selon les algorithmes.

Une sous-classe importante d'algorithmes de factorisation à usage spécifique est celle des algorithmes de catégorie 1 ou de première catégorie , dont le temps d'exécution dépend de la taille du plus petit facteur premier. Étant donné un entier de forme inconnue, ces méthodes sont généralement appliquées avant les méthodes à usage général pour supprimer les petits facteurs. la division d'essai naïve est un algorithme de catégorie 1.

• Division de première instance
• Factorisation de la roue
• L'algorithme rho de Pollard , qui a deux saveurs communes pour identifier les cycles de groupe : l'une par Floyd et l'autre par Brent.
• Algorithmes de factorisation de groupes algébriques , parmi lesquels l'algorithme p − 1 de Pollard , l'algorithme p + 1 de Williams et la factorisation de courbes elliptiques de Lenstra
• Méthode de factorisation de Fermat
• Méthode de factorisation d'Euler
• Tamis de champ de numéro spécial
• Différence de deux carrés

Un algorithme de factorisation à usage général, également connu sous le nom d' algorithme de catégorie 2 , de deuxième catégorie ou de famille Kraitchik a un temps d'exécution qui dépend uniquement de la taille de l'entier à factoriser. C'est le type d'algorithme utilisé pour factoriser les nombres RSA . La plupart des algorithmes de factorisation à usage général sont basés sur la méthode de congruence des carrés .

• Méthode de factorisation de Dixon
• Factorisation des fractions continues (CFRAC)
• Tamis quadratique
• Tamis rationnel
• Tamis de champ numérique général
• Factorisation des formes carrées de Shanks (SQUFOF)

• Algorithme de Shor , pour les ordinateurs quantiques

En théorie des nombres, il existe de nombreux algorithmes de factorisation d'entiers qui ont un temps d'exécution attendu heuristiquement

en notation little-o et L. Quelques exemples de ces algorithmes sont la méthode de la courbe elliptique et le crible quadratique . Un autre algorithme de ce type est la méthode des relations de groupe de classe proposée par Schnorr, Seysen, et Lenstra, qu'ils ont prouvée uniquement en supposant l' hypothèse de Riemann généralisée non prouvée .

L'algorithme probabiliste de Schnorr-Seysen-Lenstra a été rigoureusement prouvé par Lenstra et Pomerance comme ayant un temps d'exécution attendu L _n [ ⁠1/2⁠ , 1+ o (1)] en remplaçant l'hypothèse GRH par l'utilisation de multiplicateurs. L'algorithme utilise le groupe de classes des formes quadratiques binaires positivesdu discriminant Δ noté G _Δ . G _Δ est l'ensemble des triplets d'entiers ( a , b , c ) dans lesquels ces entiers sont premiers relatifs.

Étant donné un entier n qui sera factorisé, où n est un entier positif impair supérieur à une certaine constante. Dans cet algorithme de factorisation, le discriminant Δ est choisi comme un multiple de n , Δ = − dn , où d est un multiplicateur positif. L'algorithme s'attend à ce que pour un d il existe suffisamment de formes lisses dans G _Δ . Lenstra et Pomerance montrent que le choix de d peut être restreint à un petit ensemble pour garantir le résultat de lissage.

On note P _Δ l'ensemble de tous les nombres premiers q de symbole de Kronecker ( ⁠Δ/q⁠ ) ​​= 1. En construisant un ensemble degénérateursde G _Δ et des formes premières f _q de G _Δ avecqdans P _Δ une suite de relations entre l'ensemble des générateurs et f _q est produite. La taille deqpeut être bornée par c ₀ (log| Δ |) ² pour une certaine constante c ₀ .

La relation qui sera utilisée est une relation entre le produit de puissances qui est égal à l' élément neutre de G _Δ . Ces relations serviront à construire une forme dite ambiguë de G _Δ , qui est un élément de G _Δ d'ordre divisant 2. En calculant la factorisation correspondante de Δ et en prenant un pgcd , cette forme ambiguë fournit la factorisation première complète de n . Cet algorithme comporte les étapes principales suivantes :

Soit n le nombre à factoriser.

Pour obtenir un algorithme de factorisation de tout entier positif, il est nécessaire d'ajouter quelques étapes à cet algorithme telles que la division d'essai et le test de somme de Jacobi .

L'algorithme tel qu'il est énoncé est un algorithme probabiliste car il effectue des choix aléatoires. Son temps d'exécution prévu est au plus de L _n [ ⁠1/2⁠ , 1+ o (1)] .