Problème non résolu en informatique La factorisation d'entiers peut-elle être résolue en temps polynomial sur un ordinateur classique ? De nouveaux problèmes non résolus en info...
Worldlex WikiContenu en francaisLecture gratuite
De nouveaux problèmes non résolus en informatique
En mathématiques , la factorisation d'un entier consiste à le décomposer en un produit d'entiers. Tout entier positif supérieur à 1 est soit le produit d'au moins deux entiers supérieurs à 1, auquel cas c'est un nombre composé , soit il ne l'est pas, auquel cas c'est un nombre premier . Par exemple, théorème de la factorisation première .
Pour factoriser un petit entier la division par essais successifs : vérifier si le nombre est divisible par les nombres premiers racine carrée de à vérifier si chaque facteur est premier à chaque itération.
Tous les nombres d'une longueur donnée ne sont pas aussi difficiles à factoriser. Les cas les plus complexes (pour les techniques actuelles) sont les nombres semi-premiers , produits de deux nombres premiers. Lorsque ces deux nombres sont grands, par exemple supérieurs à deux mille bits , choisis aléatoirement et de taille comparable (mais pas trop proches, afin de ne pas empêcher une factorisation efficace par la méthode de Fermat ), même les algorithmes de factorisation en nombres premiers les plus rapides sur les ordinateurs classiques les plus performants peuvent prendre un temps tel que la recherche devient impraticable. Autrement dit, plus le nombre de chiffres de l'entier à factoriser augmente, plus le nombre d'opérations nécessaires à la factorisation sur un ordinateur classique croît de façon exponentielle.
De nombreux protocoles cryptographiques reposent sur la difficulté supposée de factoriser de grands entiers composés ou sur un problème similaire problème RSA . Un algorithme capable de factoriser efficacement un entier quelconque rendrait la cryptographie à clé publique basée sur RSA vulnérable.
théorème fondamental de l'arithmétique , tout entier positif admet une unique décomposition en facteurs premiers . (Par convention, 1 est le produit vide .) On peut vérifier si un entier est premier en temps polynomial , par exemple grâce au test de primalité AKS . En revanche, si l'entier est composé, les tests polynomiaux ne permettent pas de déterminer comment obtenir ses facteurs.
Étant donné un algorithme général de factorisation des entiers, tout entier peut être décomposé en ses facteurs premiers constitutifs par application répétée de cet algorithme. La situation est plus complexe avec les algorithmes de factorisation spécialisés, dont les avantages peuvent être moins pertinents, voire inexistants, pour les facteurs obtenus lors de la décomposition. Par exemple, si la division par essais successifs permettra d'obtenir rapidement les facteurs 3 et 19, mais nécessitera semi-premiers dont les facteurs sont de taille similaire. C'est pourquoi ce sont ces entiers qui sont utilisés dans les applications cryptographiques.
En 2019, un nombre de 240 chiffres (795 bits) ( RSA-240 ) a été factorisé par une équipe de chercheurs, dont Paul Zimmermann , en utilisant environ 900 années-cœurs de puissance de calcul. Ces chercheurs ont estimé qu'un module RSA de 1024 bits prendrait environ 500 fois plus de temps.
Le plus grand nombre semi-premier de ce type à avoir été factorisé est RSA-250 , un nombre de 829 bits comportant 250 chiffres décimaux, en février 2020. Le temps de calcul total a été d'environ 2 700 années-cœur de calcul sur un processeur Intel Xeon Gold 6130 cadencé à 2,1 GHz. Comme tous les records de factorisation récents, cette factorisation a été réalisée grâce à une implémentation hautement optimisée du crible algébrique général, exécutée sur des centaines de machines.
Complexité temporelle
Aucun algorithme capable de factoriser tous les entiers en temps polynomial , c'est-à-dire un nombre Osous-exponentiels . crible général de corps de nombres (GNFS), publié pour la première fois en 1993, s'exécutant sur un nombre de
Pour les ordinateurs actuels, GNFS est le meilleur algorithme publié pour les grandes valeurs quantique , Peter Shor a découvert en 1994 un algorithme qui le résout en temps polynomial. L'algorithme de Shor ne nécessite qu'un temps de RMN appliquées à des molécules fournissant sept qubits.
Il est connu pour appartenir à 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 test de primalité AKS, puis les multiplier pour obtenirthéorème fondamental de l’arithmétiquegarantit qu’il n’existe qu’une seule suite possible de nombres premiers croissants qui sera acceptée, ce qui montre que le problème appartient à la foisà UPet à co-UP. On sait qu’il appartient àBQPgrâce à l’algorithme de Shor.
On soupçonne que ce problème n'appartient à aucune des trois classes de complexité P, NP-complet co NP-complet . Il est donc candidat à la de complexité NP-intermédiaire .
En revanche, le problème de décision «test de primalité AKS . De plus, plusieurs algorithmes probabilistes permettent de tester la primalité très rapidement en pratique, moyennant une marge d'erreur infime. La facilité de ce test est un aspect crucial de l' algorithme RSA , car il est nécessaire de trouver de grands nombres premiers pour commencer.
Algorithmes de factorisation
Usage spécifique
Le temps d'exécution d'un algorithme de factorisation spécialisé dépend des propriétés du nombre à factoriser ou de l'un de ses facteurs inconnus : taille, forme particulière, etc. Les paramètres qui déterminent le temps d'exécution varient d'un algorithme à l'autre.
Les algorithmes de catégorie 1 (ou de première catégorie) constituent une sous-classe importante d'algorithmes de factorisation spécialisés. Leur 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 générales afin d'éliminer les petits facteurs. Par exemple, la division euclidienne est un algorithme de catégorie 1.
Un algorithme de factorisation général, également appelé algorithme de catégorie 2 , algorithme de seconde catégorie ou algorithme de la famille de 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 généraux sont basés sur la méthode de congruence des carrés .
L'algorithme probabiliste de Schnorr–Seysen–Lenstra a été rigoureusement prouvé par Lenstra et Pomerance comme ayant un temps d'exécution attendu groupe de classesformes quadratiquesbinaires positivesdudiscriminantrégulières dans symbole de Kronecker générateursdeélément neutre de PGCD , cette forme ambiguë fournit la décomposition en facteurs premiers complète de
Construisez une forme ambiguë ( a , b , c ) qui est un élément f ∈ G Δ d'ordre divisant 2 pour obtenir une factorisation copremier du plus grand diviseur impair de Δ dans lequel Δ = −4 ac ou Δ = a ( a − 4 c ) ou Δ = ( b − 2 a )( b + 2 a ) .
Si la forme ambiguë fournit une factorisation de n, alors arrêtez-vous ; sinon, recherchez une autre forme ambiguë jusqu'à ce que la factorisation de n soit trouvée. Afin d'empêcher la génération de formes ambiguës inutiles, construisez le 2- groupe de Sylow Sll 2 (Δ) de G (Δ) .
Pour obtenir un algorithme de factorisation de tout entier positif, il est nécessaire d'ajouter quelques étapes à cet algorithme telles que la division par essais successifs et le test de la somme de Jacobi .
Durée d'exécution prévue
L'algorithme tel qu'il est énoncé est un algorithme probabiliste car il effectue des choix aléatoires. Son temps d'exécution moyen est au plus
Plus d articles de Worldlex Wiki
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Worldlex Wiki