Jednocestná funkce

Jednocestná funkce je taková funkce, kterou lze snadno vyčíslit, ale je velmi obtížné (prakticky nemožné) z výsledku funkce odvodit její vstup. Ze zadaného x tedy lze snadno získat f(x), avšak výpočet inverzní funkce, získání x při znalosti f(x), je prakticky neřešitelná úloha.

Na existenci jednocestných funkcí spoléhá velká část asymetrické kryptografie.

V současné době není matematicky dokázáno, zda jednocestné funkce vůbec existují. Důkaz existence by také znamenal, že P≠NP. (Naopak ani z důkazu nerovnosti těchto tříd složitosti existence jednocestných tříd nutně nevyplývá.)

[editovat] Možné jednocestné funkce

Mezi funkce, které jsou v současné době používány jako jednocestné funkce, patří například následující:

• Násobení: Součin dvou (i velmi velkých) čísel lze spočítat snadno; nejrychlejší známý algoritmus pro rozklad velkých čísel na prvočinitele (faktorizace) vyžaduje čas , kde P je druhý největší prvočinitel faktorizovaného čísla.
• Rabinova funkce: Lze dokázat, že zjišťování druhé odmocniny modulo N je výpočetně ekvivalentní faktorizaci čísla N. Druhá mocnina na konečném tělese je tedy kandidátem na jednocestnou funkci. (Viz též kvadratické reziduum.)
• Umocňování nad konečným tělesem: Výpočet diskrétního logaritmu se obecně pokládá za náročnou úlohu.
• Za další kandidáty se považují některé NP-úplné problémy jako např. problém batohu či subset sum.

[editovat] Související články

• Hašovací funkce
• Jednocestná funkce se zadními vrátky

[editovat] Externí odkazy

• Marek Kumpošt: Hašovací funkce (bakalářská práce, Fakulta informatiky Masarykovy university, 2002)