№14 - Группы кос артина. Схема Аншель-Аншеля-Голдфельда

Группы кос Артина

Пусть
$B_{n} <\sigma_{1}, \dots,\sigma_{n-1}|\sigma_{j}\sigma_{i}=\sigma_{i}\sigma_{j}>$
при $|i-j|\geq 2,\sigma_{i}\sigma_{j}\sigma_{i}=\sigma_{j}\sigma_{i}\sigma_{j}$ при $|i-j|=1, n\geq 2$

$B_{2}=<\sigma_{1}>$ - свободная циклическая группа (циклическая группа, порожденная одним элементом). Группа бесконечная.
$B_{3}=<\sigma_{1}, \sigma_{2}|\sigma_{1}\sigma_{2}\sigma_{1}=\sigma_{2}\sigma_{1}\sigma_{2}>$
$B_{4}=<\sigma_{1},\sigma_{2},\sigma_{3}|\sigma_{1}\sigma_{3}=\sigma_{3}\sigma_{1},\sigma_{1}\sigma_{2}\sigma_{1}=\sigma_{2}\sigma_{1}\sigma_{2},\sigma_{2}\sigma_{3}\sigma_{2}=\sigma_{3}\sigma_{2}\sigma_{3}\}>$
$B_{2}\subset B_{3}\subset B_{4}\subset\dots$

Начиная с $B_{3}$ эти группы не коммутативны.

Группах $B_{n},n\geq 2$ называются группами кос Артина.
В группа кос Артина можно указать однозначные формы записи.

$\Delta_{1}\overset{\operatorname{def}}{=}1$
$\Delta_{m=1}=\Delta_{m}*\delta_{m}\delta_{m-1}\dots \delta_{1}$
$\Delta_{2}=1*\delta_{1}=\delta_{1}$
$\Delta_{3}=\delta_{1}\delta_{2}\delta_{1}$
$\Delta_{4}=\delta_{1}\delta_{2}\delta_{1}*\delta_{3}\delta_{2}\delta_{1},\dots$

Назовём элемент группы кос (косу) положительным, еси её можо записать в качестве полугруппового слова от порождающих элементов.

$(\sigma{1}\sigma_{2}^{-1}\sigma_{1}\sigma_{3}-$ групповое слово; $\sigma_{1}\sigma_{3}\sigma_{1}\sigma_{2}$ - полугрупповое слово)

Пусть $B^{+}_{n}$ - полугруппа положительных кос.

Утверждение: любую косу $b\in B_{n}$ можно записать однозначно в виде
$b=\Delta^{k}_{n}*c,$ где $k \in \mathbb{Z}$ - максимально возможный показатель, а элемент $c$ принадлежит $B^{+}_{n}$. Кроме того существует гомоморфизм $B_{n}$ в группу $S_{n}$.

Можно выбрать также элементы $b_{1},\dots,b_{e} \in B^{+}_{n}$ , $l=n!$, образы которых объективно соответствуют элементам группы $S_{n}$. Такие косы называются простыми. Каждая косы $b \in B_{n}$ допускает единственное разложение вида
$b=\Delta^{k}_{n} b_{i_{1}},\dots,b_{i_{t}},$ где $k \in \mathbb{Z}$ максимально, $b_{i_{1}},\dots,b_{i_{t}}$ - простые косы. Таким образом, канонической формой элемента $b \in B_{n}$. Процесс переписи элемента в $b$ в каноническую форму не более, чем квадратичен (???)

Протокол Аншель-Аншеля-Гольдфельда

• В качестве платформы корреспонденты $A$ и $B$ открыто выбирают группу кос $B_{n}$.
• Даллее, $A$ и $B$ выбирет наборы элементов $\bar{g}=(g_{1,\dots,g_{k}})$ и $\bar{f}=(f_{1},\dots,f_{k})$ группы $B_{n}$.
• $А$ выбирает $\bar{g}$, $B$ выбирает $\bar{f}$. Эти наборы считаются известными;
• Затем $A$ выбирает секретное слово
  $n=n(f_{1},\dots,f_{k}),$ а $B$ - секретное слово $v=v(g_{1},\dots,g_{k})$. Они могут это сделать, так как наборы $\bar{f}$ и $\bar{g}$ известны.
  Далее $A$ выполняет сопряжение набора $\bar{f}$ элементом $n$, получая набор $\bar{f}^{u}=(f^{u}_{1},\dots,f^{u}_{k})$

(Пример: $f^{u}_{1}\overset{\operatorname{def}}{=}uf_{1}u^{-1},\dots)([a,b]\overset{\operatorname{def}}{=}aba^{-1}b^{-1},[a,b]$ называется коммутатором элементов $a$ и $b$)

$A$ вычисляет и публикает нормальную форму $\text{НФ}(\bar{f}^n)=(\text{НФ}(f^n_{1}),\dots,\text{НФ}(f^n_{k}))$. Подобным образом $B$ вычисляет и публикаюте набор $\text{НФ}(\bar{g}^n_{1})=(\text{НФ}(g^n_{1}),\dots,\text{НФ}(g^n_{j}))$.

Предполагается, что в группе $B_{n}$ вычисление по опубликованным нормальным формам сопрягающих наборы элементов $n$ и $v$ - трудная задача. На этом основывается криптостойкоть протокола.

Опишем процедуру получения общего секретного ключа.

$A$ вычисляет элемент
$n(\text{НФ}(g^{v}_{1}),\dots,\text{НФ}(g^{v}_{k})).n^{-1}=n(\text{НФ}(vgv^{-1}),\dots,\text{НФ}(vg_{k}v^{-1}))n^{-1}$
Нормальная форма.
$B$ вычисляет элемент $[v,n]$ из равества $v*v(\text{НФ}(f^{u}_{1}),\dots,\text{НФ}(f^{u}_{n}))^{-1}=$
$=v*v(\text{НФ}(uf_{1}u^{-1},\dots,\text{НФ}(uf_{k}u^{-1})))^{-1}=$
$=v*(nv(f_{1},\dots,f_{k})n^{-1})^{-1}=$
$=vkv^{-1}u^{-1}=v(f_{1},\dots,f_{k}$