From Wikipedia, the free encyclopedia
Jednosměrná funkce, někdy též jednocestná funkce, je taková funkce, kterou lze snadno vyčíslit, ale je velmi obtíž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 sice teoreticky možné, ale prakticky velmi obtížné. Důvodem je existence velmi vysokého počtu možných řešení, přičemž je nutné všechny ověřit, aby skutečné řešení bylo nalezeno a toto ověření by trvalo neúměrně dlouho (v praxi se požadují tisíce, miliardy i více let).
Na existenci jednosměrných funkcí spoléhá velká část asymetrické kryptografie.
V současné době není matematicky dokázáno, zda jednosměrné 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 jednosměrných funkcí nutně nevyplývá).
Mezi funkce, které jsou v současné době používány jako jednosměrné funkce, patří například následující:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.