Список обозначений

Параметр полиномиальный

polynomial parameter
Функция $k\colon\mathbb N\to\mathbb N$ называется полиномиальным параметром, если функция $1^n\mapsto1^{k(n)}$ ($n\in\mathbb N$) полиномиально вычислима. Это условие выполнено тогда и только тогда, когда функция $k$ полиномиально ограничена (т. е. существует полином $p$ такой, что $k(n)\leqslant p(n)$ для всех $n\in\mathbb N$) и вычислима детерминированным алгоритмом за полиномиальное от $n$ время. См. [1].

Литература

  • [1] Luby, M. «Pseudorandomness and cryptographic applications» 1996

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна