Funció parany

De Viquipèdia
Dreceres ràpides: navegació, cerca

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.