Funció parany

De Viquipèdia
Jump to navigation Jump to search

Una funció parany és una funció matemàtica el càlcul directe de la qual és senzill, però en la qual el càlcul de la funció inversa és molt complex; és a dir, involucra un elevat nombre d'operacions, per exemple, exponencial. Són especialment utilitzades en criptografia.

A títol d'exemple, es pot considerar el producte de nombres primers:

(p, q) &*rarr; m = p. q

L'operació anterior és molt ràpida, però l'operació inversa, és a dir, donat m trobar p i q, és, en general, de complexitat exponencial en la longitud de m. Per exemple, si m té 100 xifres, el nombre mitjà d'operacions requerides per a factorizar m seria 1050 operacions, de forma que un ordinador que faci 1 milió d'operacions per segon trigaria més de 1036 anys. En aquest cas, m seria utilitzat com a clau pública, mentre que els nombres primers (p,q) serien la clau privada.