Меню Главная Случайная статья Настройки Трудный бит Материал из https://ru.wikipedia.org В криптографии, трудным предикатом для односторонней функции ${\displaystyle f}$ называется функция ${\displaystyle h}$, принимающая значение 0 или 1, при этом её значение ${\displaystyle h(x)}$ легко вычислить зная ${\displaystyle x}$, и трудно вычислить зная лишь ${\displaystyle f(x)}$. Формально, полиномиально вычислимая функция ${\displaystyle h_{n}:D_{n}{\xrightarrow[{}]{}}\{0,1\}}$ является трудным предикатом для функции ${\displaystyle f_{n}:D_{n}{\xrightarrow[{}]{}}D_{n}}$, если случайная величина ${\displaystyle h_{n}(\alpha _{n})}$ трудно вычислима по случайной величине ${\displaystyle f_{n}(\alpha _{n})}$, где ${\displaystyle \alpha _{n}}$ — случайная величина, равномерно распределённая на ${\displaystyle D_{n}}$. См. также Криптографическая хеш-функция Ссылки Гирш Э. А. «Сложность вычислений и основы криптографии». Курс лекций описывающий основы сложности вычислений и криптографии. Верещагин Н. К. Конспект лекций курса по криптографии.