Односторонняя функция: различия между версиями

[непроверенная версия][отпатрулированная версия]
Содержимое удалено Содержимое добавлено
м https://foundation.wikimedia.org/wiki/Terms_of_Use/ru
м откат правок Vikaevgenii (обс.) к версии InternetArchiveBot
Метка: откат
Строка 1:
{{unsolved|информатики|'''''Существуют ли односторонние функции ?'''''}}
'''[[Односторонняя скорость света|Односторонняя]]'''<ref>{{Книга|ссылка=http://worldcat.org/oclc/1185584125|автор=Стринкевич, Эльвира Verfasser|заглавие=Диагностическая значимость отоакустической эмиссии Диагностическая значимость отоакустической эмиссии при кохлеовестибулярных нарушениях|isbn=978-3-659-27119-9, 3-659-27119-5}}</ref><ref>{{Статья|ссылка=http://dx.doi.org/10.18698/0236-3933-2018-5-84-98|автор=С.В. Зуев|заглавие=Generalised Quantum Hash Function and Secure One-Way Data Transmission|год=2018-10|издание=Herald of the Bauman Moscow State Technical University. Series Instrument Engineering|выпуск=122|issn=0236-3933|doi=10.18698/0236-3933-2018-5-84-98}}</ref> '''функция''' — [[Функция (математика)|математическая функция]], которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения [[Теория сложности вычислений|теории сложности вычислений]]. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. [[Инъекция (математика)|Неинъективность функции]] не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.
 
Существование односторонних функций до сих пор не доказано. Их существование докажет, что [[Равенство классов P и NP|классы сложности P и NP не равны]], попутно разрешив ряд вопросов теоретической [[Информатика|информатики]]. Современная{{когда}} [[асимметричная криптография]] основывается на предположении, что односторонние функции всё-таки существуют.