Funció trampa

Una funció trampa consistix en una funció matemàtica el càlcul directe de la qual és senzill, pero en la que el càlcul de la funció inversa és molt complex, és dir, involucra un elevat número (per eixemple, exponencial) d'operacions.

A modo d'eixemple, considerem el producte d'número primo

(p, q) → m = p · q

L'operació anterior és molt ràpida, pero l'operació inversa, és dir, donat m trobar p i q, és (en general) de complexitat exponencial en la llongitut de m. Per eixemple, si m té 100 sifres, el número mig d'operacions requerides per a factorizar m seria 10^50 operacions, en lo que un ordenador que faça 1 milló d'operacions per segon tardaria més de 10^36 anys.

En este cas, m seria utilisat com a clau pública en criptografia asimètrica, mentres que els número primo (p,q) serien la clau privada.

Vore també

• Criptografia asimètrica