Fer que els codis secrets siguin irrompibles és el somni de tota la vida dels professionals de la seguretat. Des de l'antiguitat, els humans van inventar sistemes manuals i després mecànics abans de la revolució electrònica. Descobreix la criptologia i els seus usos, des del xifratge tradicional fins al xifratge RSA i la informàtica.
La criptografia contemporània es basa en funcions unidireccionals. Aquestes funcions es calculen fàcilment, però és pràcticament impossible, donat un valor, trobar el paràmetre que ha portat a aquest valor. Per exemple, si es trien dos nombres primers grans, és fàcil multiplicar-los. Actualment, però, el producte per si sol no ens permet trobar els factors si aquests es trien perquè siguin prou grans. La multiplicació d'enters és una funció unidireccional. És un cas especial de problemes que no sabem com resoldre però, un cop coneguda la solució, és fàcil de verificar.
Si et repten, per exemple, a factoritzar el nombre 2.027.651.281, probablement tindries moltes dificultats per trobar els factors sense una eina de càlcul potent. D'altra banda, si et digués que aquests factors són 46.061 i 44.021, només necessitaries un minut per verificar que aquesta solució és correcta.
Clic a la imatge per engrandir. Recreació artística de la màquina de Turing (sense la taula de transició). Crèdit: Schadel, DP
La preocupació és que l'existència d'aquests problemes no és certa. Els investigadors encara no han pogut demostrar que la factorització de nombres enters sigui realment un problema difícil. L'única observació que podem fer és que, en l'estat actual dels nostres coneixements, aquest problema està lluny de ser fàcil de resoldre. S'han fet nombrosos i impressionants avenços des que els matemàtics s'hi van interessar per primera vegada. La resolució en només unes dècades, d'una complexitat de la factorització ha passat d'exponencial a subexponencial depenent del nombre de dígits del nombre a factoritzar. El progrés s'aturarà aquí o encara cal esperar més avenços?
Encara es desconeix si és simplement el nostre desconeixement d'algoritmes més eficients el que dificulta la factorització, o si aquesta dificultat rau en la naturalesa mateixa del problema. Les nocions de computabilitat i complexitat computacional van ser modelades per
Alan Turing en una màquina abstracta. La màquina de Turing inclou:
- Una unitat central de càlcul que pot estar en un nombre finit d'estats;
- Una cinta il·limitada on inicialment es contenen les dades que s'han de processar i on s'escriuen els resultats; aquestes dades s'expressen mitjançant un alfabet de mida finita;
- Un capçal de lectura-escriptura que pot substituir un caràcter per un altre a la cinta o moure la cinta una posició cap a l'esquerra o cap a la dreta.
El programa d'una màquina d'aquest tipus és una llista d'instruccions, cadascuna de les quals consta de quatre informacions: un estat
q, un símbol
s, un nou estat
r i una acció
a del capçal de lectura. Si la màquina es troba en l'estat
q i llegeix el símbol
s de la cinta, passa a l'estat
r i realitza l'acció
a, que consisteix a escriure un símbol
a la cinta en lloc de
s desplaçant la cinta en una direcció o altra.
Es diu que una
màquina de Turing és "determinista" si el seu programa consisteix en només una instrucció per a un estat i símbol determinats. Un problema pertany a la classe P (de "polinomi") si existeix una màquina de Turing determinista que el resol executant un nombre d'instruccions delimitades per un polinomi de la mida de les dades. Un problema que no pertany a aquesta classe es considerarà difícil, almenys per a algunes dades.
Si, en canvi, hi ha diverses instruccions possibles corresponents a un estat i símbol determinats, es diu que la màquina és "no determinista". Una màquina no determinista resol el problema si existeix una seqüència d'instruccions que condueix al resultat, en altres paraules, si existeix un oracle que indica a la màquina quina instrucció ha d'executar d'entre diverses opcions possibles. Una màquina no determinista es pot simular amb un nombre il·limitat de màquines deterministes, cadascuna de les quals tria una de les instruccions per executar-la en un estat determinat. Un problema pertany a la classe NP si existeix una màquina de Turing no determinista que el resol en un nombre d'instruccions delimitades per un polinomi de la mida de les dades. Aquests són precisament els problemes que es verifiquen fàcilment, la solució actua com un oracle que indica l'elecció d'instruccions que condueixen al resultat.
Si un problema pertany a la classe P, aleshores també pertany a la classe NP. Un dels principals problemes oberts en la teoria de la complexitat és si la classe NP és estrictament més gran que la classe P o no, una qüestió que es pot resumir de la següent manera: existeix algun problema fàcilment verificable que sigui difícil de resoldre?
Si existeix un problema d'aquest tipus, que encara no s'ha demostrat, la factorització dels enters és un candidat probable.
