WikiSort.ru - Не сортированное

Группа кос

Пусть n- положительное целое число. Группа кос B_n можно задать (n − 1) образующими и ${\displaystyle {\tfrac {n\cdot (n-1)}{2}}}$ соотношениями:^[3]

• ${\displaystyle B_{n}=\langle \sigma _{1},\ldots ,\sigma _{n-1}\ \mid \ \sigma _{i}\sigma _{i+1}\sigma _{i}=\sigma _{i+1}\sigma _{i}\sigma _{i+1}\ {\text{при}}\ 1\leq i\leq n-2\ {\text{и}}\ \sigma _{i}\sigma _{j}=\sigma _{j}\sigma _{i}\ {\text{for}}\ |i-j|\geq 2\rangle :}$

В частности, любой элемент B₄ можно записать как композицию следующих трёх элементов (и обратных к ним):

σ1	σ2	σ3

Группа Томпсона

Группа Томпсона является бесконечной группой F, имеющей следующее бесконечное представление:^[4]

${\displaystyle F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_{n+1}{\text{ for }}k<n\right\rangle }$

Группа Григорчука

Пусть T обозначает бесконечное корневое двоичное дерево. Множество V вершин - это множество всех конечных двоичных последовательностей. Пусть A(T) обозначает множество всех автоморфизмов T. (Автоморфизм T переставляет вершины, сохраняя связность.) Группа Григорчука Γ - подгруппа A(T), порождаемая автоморфизмами a, b, c, d, определяющимися следующим образом:

• ${\displaystyle a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})}$
• ${\displaystyle b(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},c(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$
• ${\displaystyle c(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},d(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$
• ${\displaystyle d(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},b(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$

Группа Артина

Группа Артина A(Γ) - это группа со следующим представлением:^[5]

${\displaystyle {\begin{aligned}{\Big \langle }x_{1},x_{2},\ldots ,x_{n}{\Big |}\langle x_{1},x_{2}\rangle ^{m_{1,2}}&=\langle x_{2},x_{1}\rangle ^{m_{2,1}},\ldots \\&\ldots ,\langle x_{n-1},x_{n}\rangle ^{m_{n-1,n}}=\langle x_{n},x_{n-1}\rangle ^{m_{n,n-1}}{\Big \rangle }\end{aligned}}}$

где

${\displaystyle m_{i,j}=m_{j,i}\in \{2,3,\ldots ,\infty \}.}$

Для ${\displaystyle m<\infty }$ , ${\displaystyle \langle x_{i},x_{j}\rangle ^{m}}$ обозначает знакопеременное произведение ${\displaystyle x_{i}}$ и ${\displaystyle x_{j}}$ длинной ${\displaystyle m}$ , начиная с ${\displaystyle x_{i}}$ . Например,

${\displaystyle \langle x_{i},x_{j}\rangle ^{3}=x_{i}x_{j}x_{i}}$

и

${\displaystyle \langle x_{i},x_{j}\rangle ^{4}=x_{i}x_{j}x_{i}x_{j}.}$

Если ${\displaystyle m=\infty }$ , тогда (по соглашению) нет никакого отношения между ${\displaystyle x_{i}}$ и ${\displaystyle x_{j}}$ .

Матричные группы

Пусть F-конечное поле. Группы матриц над F были использованы в качестве базовых групп некоторых некоммутативных криптографических протоколов.

Протоколы для обмена ключами

Протоколы шифрования и дешифрования

Этот протокол описывает, как зашифровать секретное сообщение, а затем расшифровать его с помощью некоммутативной группы. Пусть Алиса хочет отправить Бобу секретное сообщение m.

1. Пусть G - некоммутативная группа. Также, пусть A и B будут публичными подгруппами из G для которых верно: ab = ba для всех a из A и b из B.
2. Элемент x из G выбран и опубликован.
3. Боб выбирает секретный ключ b из A и публикует z = x^b как свой открытый ключ.
4. Алиса выбирает случайный r из B и вычисляет t = z^r.
5. Зашифрованным сообщение является C = (x^r, H(t) ${\displaystyle \oplus }$ m), где H это некоторая хеш-функция и ${\displaystyle \oplus }$ обозначает операцию XOR. Алиса отправляет C Бобу.
6. Чтобы расшифровать C, Боб восстанавливает t через: (x^r)^b = x^rb = x^br = (x^b)^r = z^r = t. Текстовое сообщение отправленное Алисой вычисляется как P = ( H(t) ${\displaystyle \oplus }$ m ) ${\displaystyle \oplus }$ H(t) = m.

Протоколы аутентификации

Боб хочет проверить, действительно ли отправителем сообщения является Алиса.

1. Пусть G - некоммутативная группа. Также, пусть A и B будут подгруппами из G для которых верно: ab = ba для всех a из A и b из B.
2. Элементw из G выбран и опубликован.
3. Алиса выбирает секретный s из A и публикует пару ( w, t ) где t = w ^s.
4. Боб выбирает r из B и посылает сообщение w ' = w^r Алисе.
5. Алиса отправляет ответw ' ' = (w ')^s Бобу.
6. Боб проверяет равенство w ' ' = t^r. Если равенство выполняется, то личность Алисы подтверждается.