Factorisation des entiers

Considérons un nombre entier, très grand, dont on sait qu'il est le produit de deux nombres premiers, mais on ne sait pas lesquels. Le problème de la factorisation est de trouver ces deux nombres. C'est un problème simple à poser, mais difficile à résoudre. En effet, s'il faut n chiffres pour écrire notre nombre, on ne connaît encore aucune méthode, ni à la main, ni avec les ordinateurs actuels, qui garantisse qu'on puisse trouver ces deux facteurs en effectuant moins de e^n/3 opérations élémentaires (e = 2,71828...) : les seuls algorithmes connus pour la factorisation sont de complexité exponentielle.
Paradoxalement, l'obstacle que constitue cette complexité présente un grand intérêt, car c'est précisément sur la difficulté à le franchir que repose la sécurité des systèmes de cryptage les plus répandus, comme ceux qui sont utilisés sur internet pour transmettre des informations confidentielles.