Funzione unidirezionale
funzione facile da calcolare, ma difficile da invertire / Da Wikipedia, l'enciclopedia encyclopedia
Caro Wikiwand AI, Facciamo breve rispondendo semplicemente a queste domande chiave:
Puoi elencare i principali fatti e statistiche su Funzioni unidirezionali?
Riassumi questo articolo per un bambino di 10 anni
Una funzione unidirezionale (funzione one-way in inglese o semplicemente OWF) è una funzione matematica "facile da calcolare" ma "difficile da invertire"[1][2].
"Facile da calcolare" significa che esistono algoritmi che possono calcolare la funzione f(x) in tempo polinomiale (nella dimensione dell'input). "Difficile da invertire" significa che nessun algoritmo probabilisticamente polinomiale (classe di complessità temporale PP) può calcolare una controimmagine di f(x) a meno di una probabilità trascurabile, quando x viene scelta in modo casuale.
Si noti che, a differenza del concetto di difficoltà più comunemente diffuso nella teoria della complessità computazionale, "difficile", nel contesto delle funzioni unidirezionali, si riferisce alla difficoltà nel caso medio e non a quella nel caso peggiore.