← Unknownpedia : voir sur la carte
Peut-on factoriser rapidement un grand nombre avec un ordinateur ordinaire ?
Question ouverte
On ne connaît aucun algorithme rapide, et une grande part du chiffrement repose sur cette difficulté. Un ordinateur quantique pourrait le faire vite (algorithme de Shor).
Brouillon rédigé avec une IA (Claude). Les références existent, vérifiées dans OpenAlex ; le texte n’a pas encore été relu par un spécialiste. Qui écrit quoi
Ce qu'on sait
- Tout entier supérieur à 1 s'écrit de façon unique comme un produit de nombres premiers. Pour de petits nombres, trouver ces facteurs est facile.
- Pour de très grands nombres (des centaines de chiffres), les meilleurs algorithmes connus sur un ordinateur ordinaire demandent un temps qui explose avec le nombre de chiffres.
- Des systèmes de chiffrement très répandus, comme RSA, reposent sur cette difficulté.
- En 1994, Peter Shor a montré qu'un ordinateur quantique assez grand saurait factoriser vite.
Ce qu'on ignore
- S'il existe un algorithme rapide pour un ordinateur ordinaire. Personne n'en connaît, et personne n'a montré qu'il n'en existe pas.
- Si la factorisation est aussi difficile que les problèmes les plus durs de la classe NP. On pense que non, sans l'avoir démontré.
Pourquoi c'est dur
- Prouver qu'aucun algorithme, même inconnu, ne réussit : on ne sait le faire pour presque aucun problème.
- Ce problème a une structure particulière qui le rend probablement plus facile que les problèmes NP-complets, sans qu'on sache pour autant qu'il est facile.
Pourquoi ça compte
La sécurité d'une grande partie du chiffrement actuel. C'est ce qui motive les travaux sur la cryptographie capable de résister aux ordinateurs quantiques.
Par où commencer
- La théorie de la complexité et la théorie des nombres.
- Un premier pas : factoriser 91, puis 8 633 à la main, et constater comme l'effort grandit.
- Les deux articles ci-dessous : celui de Shor sur le calcul quantique, et celui qui a introduit RSA.
Pour aller plus loin
En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 32 × 5, soit 3 × 3 × 5.
Extrait de l'article Wikipédia « Décomposition en produit de facteurs premiers » (licence CC BY-SA).
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Peter W. Shor, 1997 - A method for obtaining digital signatures and public-key cryptosystems
Ronald L. Rivest, Adi Shamir, Leonard M. Adleman, 1978