b'\n_START_ARTICLE_\nFunkcja jednokierunkowa\n_START_PARAGRAPH_\nFunkcja jednokierunkowa \xe2\x80\x93 funkcja, kt\xc3\xb3ra jest \xc5\x82atwa do wyliczenia, ale trudna do odwr\xc3\xb3cenia. \xe2\x80\x9e\xc5\x81atwa do wyliczenia\xe2\x80\x9d oznacza tu, \xc5\xbce istnieje algorytm wielomianowy, kt\xc3\xb3ry j\xc4\x85 wylicza. \xe2\x80\x9eTrudna do odwr\xc3\xb3cenia\xe2\x80\x9d oznacza, \xc5\xbce \xc5\xbcaden wielomianowy algorytm probabilistyczny nie potrafi znale\xc5\xba\xc4\x87 elementu przeciwobrazu  z prawdopodobie\xc5\x84stwem wi\xc4\x99kszym ni\xc5\xbc zaniedbywalne, je\xc5\x9bli  jest wybrane losowo. Trudno\xc5\x9b\xc4\x87 dotyczy zatem \xc5\x9bredniego przypadku, a nie pesymistycznego, jak w wi\xc4\x99kszo\xc5\x9bci problem\xc3\xb3w w teorii z\xc5\x82o\xc5\xbcono\xc5\x9bci obliczeniowej (np. w problemach NP-trudnych).\n_START_SECTION_\nKandydaci na funkcje jednokierunkowe\n_START_PARAGRAPH_\nPoniewa\xc5\xbc do tej pory nie wiadomo, czy funkcje jednokierunkowe istniej\xc4\x85, w praktyce u\xc5\xbcywa si\xc4\x99 kilku funkcji, kt\xc3\xb3re s\xc4\x85 o to podejrzewane: funkcji, dla kt\xc3\xb3rych pomimo wysi\xc5\x82ku wielu badaczy nie uda\xc5\x82o si\xc4\x99 znale\xc5\xba\xc4\x87 efektywnych algorytm\xc3\xb3w odwracaj\xc4\x85cych.\n_START_SECTION_\nMno\xc5\xbcenie vs. faktoryzacja\n_START_PARAGRAPH_\nMno\xc5\xbcenie liczb naturalnych jest \xc5\x82atwe algorytmicznie. Z drugiej strony je\xc5\x9bli pomno\xc5\xbcymy przez siebie dwie du\xc5\xbce liczby pierwsze (np. 34961 i 49369, wynik mno\xc5\xbcenia to 1725989609), znalezienie ich na podstawie iloczynu mo\xc5\xbce by\xc4\x87 trudne. Mno\xc5\xbcenie mo\xc5\xbce by\xc4\x87 wi\xc4\x99c funkcj\xc4\x85 s\xc5\x82abo jednokierunkow\xc4\x85. Na tej funkcji opiera si\xc4\x99 w du\xc5\xbcej mierze kryptosystem RSA._NEWLINE_Obecnie najlepszym znanym algorytmem faktoryzacji jest GNFS, kt\xc3\xb3rego z\xc5\x82o\xc5\xbcono\xc5\x9b\xc4\x87 wynosi\n_START_SECTION_\nFunkcja Rabina\n_START_PARAGRAPH_\nJe\xc5\x9bli dla danego  i  wyliczymy  (mod N), to mo\xc5\xbcna pokaza\xc4\x87, \xc5\xbce znalezienie  na podstawie y jest algorytmicznie r\xc3\xb3wnie trudne jak faktoryzacja  Podnoszenie do kwadratu jest wi\xc4\x99c r\xc3\xb3wnie dobrym kandydatem na funkcj\xc4\x99 jednokierunkow\xc4\x85 jak mno\xc5\xbcenie. Na tej funkcji oparty jest kryptosystem Rabina.\n_START_SECTION_\nPot\xc4\x99gowanie vs. logarytm dyskretny\n_START_PARAGRAPH_\nJe\xc5\x9bli dla danej liczby pierwszej  oraz  i  wyliczymy (mod p), to okazuje si\xc4\x99, \xc5\xbce nie znamy efektywnego algorytmu pozwalaj\xc4\x85cego znale\xc5\xba\xc4\x87 w\xc5\x82a\xc5\x9bciwe  na podstawie   i  Pot\xc4\x99gowanie w ciele sko\xc5\x84czonym jest wi\xc4\x99c kandydatem na funkcj\xc4\x99 jednokierunkow\xc4\x85. Opiera si\xc4\x99 na nim kryptosystem ElGamal.\n_START_SECTION_\nInne funkcje\n_START_PARAGRAPH_\nWszystkie trzy podane wy\xc5\xbcej funkcje mog\xc4\x85 by\xc4\x87 funkcjami jednokierunkowymi, ale wiadomo ju\xc5\xbc, \xc5\xbce mo\xc5\xbcna je \xc5\x82atwo odwraca\xc4\x87, je\xc5\x9bli ma si\xc4\x99 do dyspozycji komputer kwantowy (u\xc5\xbcywaj\xc4\x85c Algorytmu Shora do faktoryzacji i kwantowej transformaty Fouriera do wyliczenia logarytmu dyskretnego). Istniej\xc4\x85 inne funkcje podejrzewane o bycie funkcjami jednokierunkowymi, np. bazuj\xc4\x85ce na r\xc3\xb3\xc5\xbcnych problemach NP-zupe\xc5\x82nych. W praktyce ich bezpiecze\xc5\x84stwo jest jednak znacznie s\xc5\x82abiej zbadane.'