Еднопосочен функция - studopediya

Наречен еднопосочен функция F: X → Y. има две свойства:

а) има полином алгоритъм за изчисляване на стойностите на F (х);

б) има полином алгоритъм обръщане функция F. т.е. решаване на уравнение F (х) = у по отношение на х.

Неформално казано, P е класа на проблеми с полином сложност. По-точно, клас P - е класа на езика. разпознаваема в полином време на детерминирана машина Тюринг. Ако една машина на Тюринг за допълване на хипотетичен способността да "Предполагам, че" е по-мощен модел - не-детерминирана машина Тюринг. NP клас - това е класа на езици разпознаваеми в полином време на която не е детерминирана машина Тюринг. съвпадение проблемни класове P и NP - това е проблем на корелация разполага с две изчислителни модели: детерминирана и не-детерминирана машина Тюринг.

Друга идея по-близо до традиционната криптографията, в който таен ключ, е концепцията за еднопосочен функция с тайно. Понякога дори се използва терминът функция с капан. функция врата вертикална тръба (английски име: един # 8209; начин капан # 8209; функция врата).

Еднопосочен функция с тайно K е функция F K. X → Y. в зависимост от параметъра К и има три свойства:

а) за всяко К има полином алгоритъм за изчисляване на стойностите F К (х);

б) когато неизвестен K не съществува полином алгоритъм обръщане F К;

в) с известна К съществува полином алгоритъм обръщане F K.

За съществуването на еднопосочна функция с тайно, може да се каже едно и също нещо, което беше казано по-рано за еднопосочни функции. За практически цели криптография няколко функции са били построени, които могат да бъдат едностранно. Това означава, че за тях имот б) докато не строго доказано, но е известно, че проблемът с инверсия е равностойно на дългосрочен учи трудно математическа задача. Примери на тези функции са показани на скиците 3.5, 3.6, 3.7. Заслужава да се отбележи, че за някои кандидати за еднопосочен функцията са открити полином алгоритми, за да обърнете и по този начин се оказа, че тези функции не са едностранни.