Le cryptage RSA repose sur le problème de la factorisation d'un grand nombre en ses éléments premiers.
À l'heure actuelle, on ne sait pas factoriser des grands nombres. Cependant, on ne sait pas si ce problème est réellement difficile, ou si on s'y prend tout simplement mal depuis 3000 ans.
À vrai dire, il n'est pas interdit qu'un jour prochain quelqu'un décrouvre une méthode rapide et systèmatique de décomposition d'un nombre en ses facteurs premiers. On aurait tous du mauvais sang à se faire...
Le problème du sac à dos, lui, est démontré réellement difficile. Le problème est, ici, que l'on n'arrive pas à construire un cryptosystème fiable sur ce problème.
Évoquons, pour finir, le nom de la conjecture de Riemann, qui a un énoncé abscond, mais dont la résolution, pour d'obscures raisons, permettraient de résoudre le problème de la factorisation. Une médaille fields sur deux a été décernée à des mathématiciens ayant fait avancer la recherche sur cette conjecture.