Egyirányú függvény - studopediya

Úgynevezett egyirányú függvény F: X → Y. két tulajdonsága van:

a) van egy polinomiális algoritmus kiszámításához értékeinek F (x);

b) van egy polinomiális algoritmus invertáló funkció F. azaz megoldása az egyenlet F (x) = y tekintetében x.

Informálisan elmondható, hogy P az osztály a problémák egy polinomiális komplexitás. Pontosabban, az osztály P - a nyelvek osztályát. felismerhető polinomiális determinisztikus Turing-gép. Ha egy Turing-gép, hogy kiegészítse a hipotetikus képességét, hogy „kitalálni” egy erősebb modellt - egy nem determinisztikus Turing-gép. Osztály NP - ez a nyelvek osztályát felismerhető polinomiális időben egy nem-determinisztikus Turing-gép. illő probléma P és NP osztályok - ez a probléma a korrelációs funkciók két számítási modellek: determinisztikus és nem-determinisztikus Turing-gép.

Egy másik koncepció közelebb hagyományos titkosítás, amelyben egy titkos kulcsot, a koncepció a egyirányú függvény egy titkot. Néha még használta ezt a kifejezést funkció csapda. függvény ajtó standpipe (angol neve: egy # 8209; módon csapda # 8209; ajtófunkciót).

Egyirányú függvény egy titkos K függvénye F K. X → Y. attól függően, hogy a K paraméter, és három tulajdonságok:

a) bármely K van egy polinomiális algoritmust az értékek F K (x);

b) ha egy ismeretlen K nincs polinomiális algoritmus megfordításával F K;

c) egy ismert K létezik olyan polinomiális algoritmus invertáló F K.

A létezéséről egyirányú függvény egy titkos, akkor ugyanazt mondják, amit mondott korábban a egyirányú függvények. Gyakorlati célokra kriptográfia számos funkciót építettek, amely lehet egyoldalú. Ez azt jelenti, hogy számukra az ingatlan b) nem feltétlenül bizonyult, de azt tudjuk, hogy a probléma az inverzió egyenértékű hosszú tanulmányozott nehéz matematikai probléma. Példák az ilyen funkciót is feltüntettünk, a vázlatok 3.5, 3.6, 3.7. Érdemes megjegyezni, hogy egyes jelölteket az egyirányú függvény polinom algoritmusok talált megfordítani és ezzel bebizonyította, hogy ezek a funkciók nem egyoldalú.