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

Семейство групп полиномиально вычислимое

polynomial-time computable family of groups
Пусть $I$ — подмножество $\{0,1\}^*$ или $\mathbb N$. Для произвольного $i\in I$ положим $\rho(i)=i$, если $I\subseteq\{0,1\}^*$, и $\rho(i)=1^i$, если $I\subseteq\mathbb N$. Тогда семейство $(G_i\,|\, i\in I)$ групп, носители которых содержатся в $\{0,1\}^*$, называется полиномиально вычислимым, если функции
  • $(\rho(i),x,y)\mapsto xy$ в $G_i$ ($i\in I$, $x,y\in G_i$),
  • $(\rho(i),x)\mapsto x^{-1}$ в $G_i$ ($i\in I$, $x\in G_i$),
  • $\rho(i)\mapsto 1$ в $G_i$ ($i\in I$)
полиномиально вычислимы.
Пример 1
Семейство групп \[ \left(\left.\mathbb Z^{\star}_{\operatorname{num}(i)}\,\right|\,i\in\{0,1\}^*\right) \] полиномиально вычислимо.

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