Интернет магазин китайских планшетных компьютеров

Компьютеры - Односторонняя функция

Нерешённые проблемы computer science: ''Существуют ли односторонние функции ?''

Односторонняя функция это функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней.

Существование односторонних функций до сих пор не доказано. Фактически, их существование докажет, что классы сложности P и NP не равны, попутно разрешив ряд вопросов теоретической информатики. Современная асимметричная криптография основывается на предположении, что односторонние функции все-таки существуют.

Односторонние функции являются фундаментальными инструментами криптографии, персональной идентификации, аутентификации и других областей защиты данных. Хотя существование таких функций по прежнему остается недоказанной гипотезой, существует несколько претендентов, выдержавших десятилетия пристального изучения. Многие из них являются неотъемлемой частью большинства телекоммуникационных систем, а также систем электронной коммерции и интернет-банкинга по всему миру.