Funzione unidirezionale
Una funzione facile da calcolare in avanti ma praticamente impossibile da invertire.
Moltiplicando due numeri primi grandi si ottiene il prodotto in una frazione di secondo. Fattorizzarlo può richiedere anni, a seconda della dimensione dei numeri. Le funzioni unidirezionali sono alla base di hashing, archiviazione delle password e firme digitali. Si conserva l'hash anziché la password, perciò chi ruba il database ottiene una funzione che non può eseguire al contrario.
Nessuno ha dimostrato che le funzioni unidirezionali esistano. È un'assunzione, e una dimostrazione proverebbe anche che P è diverso da NP. La crittografia poggia dunque su qualcosa in cui crediamo ma che non sappiamo ancora dimostrare, posizione scomoda per una disciplina che ama le dimostrazioni.