1.3. Quasigroup

Định nghĩa 1.27 (Quasigroup)

Tập \(Q\) và phép toán hai ngôi \(\star\) được gọi là quasigroup (hay квазигруппа) nếu với mọi \(a, b \in Q\), tồn tại duy nhất hai phần tử \(x, y \in Q\) sao cho

\[a \star x = b, \quad y \star a = b.\]

Ví dụ 1.20

Mọi nhóm đều là quasigroup.

Ví dụ 1.21

\((\mathbb{Z}, -)\) không phải là nhóm nhưng là quasigroup.

Chứng minh

Với mọi \(a, b, \in \mathbb{Z}\) ta tìm \(x\), \(y\) sao cho \(a - x = b\) và \(y - a = b\).

Khi đó \(x = a - b\) và \(y = a + b\), nói cách khác là tồn tại hai phần tử duy nhất \(x\), \(y\)

Nhận xét 1.6

Quasigroup không có tính kết hợp nên chúng ta không thể định nghĩa phép tính \(a^n\) như với nhóm.

Định nghĩa 1.28 (\(d\)-quasigroup)

Xét quasigroup \((Q, g)\) với \(g\) là ánh xạ

\[g: Q^d \to Q, \quad d \geqslant 2\]

được gọi là \(d\)-quasigroup và \(g\) được gọi là toán tử quasigroup.

Định nghĩa quasigroup ở đầu bài tương ứng với \(d = 2\) (với \(g\) là toán tử hai ngôi).

Định nghĩa 1.29 (Bảng Latin)

Bảng Latin là bảng gồm \(k\) hàng và \(k\) cột. Ta viết các số từ \(0\) tới \(k - 1\) lên bảng sao cho mỗi hàng có \(k\) phần tử khác nhau và mỗi cột cũng có \(k\) phần tử khác nhau.

Ví dụ, với \(k = 2\) ta có bảng

\(0\)	\(1\)
\(1\)	\(0\)

Ví dụ, với \(k = 3\) ta có bảng

\(0\)	\(2\)	\(1\)
\(1\)	\(0\)	\(2\)
\(2\)	\(1\)	\(0\)

Mỗi ô được biểu diễn bởi bộ ba (тройка) \((i, j, t)\) với

• \(i\) là vị trí hàng;

• \(j\) là vị trí cột;

• \(t\) là giá trị tại ô \((i, j)\).

Định nghĩa 1.30 (Homotopy)

Giả sử \((P, \star)\) và \((Q, *)\) là hai quasigroup. Khi đó quasigroup homotopy từ \(P\) tới \(Q\) là bộ ba \((\alpha, \beta, \gamma)\) biểu diễn ba ánh xạ từ \(P\) tới \(Q\) thỏa

\[\alpha(x) * \beta(y) = \gamma(x \star y)\]

với mọi \(x, y \in P\).

Định nghĩa 1.31 (Isotopy)

Khi cả ba ánh xạ \(\alpha\), \(\beta\) và \(\gamma\) đều là song ánh thì ta nói homotopy là isotopy (hay изотопия).

Định nghĩa 1.32 (Autotopy)

Autotopy là isotopy tới chính nó, nghĩa là \(P \equiv Q\).

Nhận xét 1.7

Isotopy là quan hệ tương đương.

\[Q_1 \sim Q_2 \Longleftrightarrow Q_1 \ \text{isotopy với} \ Q_2.\]

Định nghĩa 1.33 (Parastrophe)

Từ toán tử ban đầu \(\star\) ta định nghĩa thêm năm toán tử khác là:

1. Toán tử \(\circ\) với \(x \circ y = y \star x\) là toán tử đối của toán tử \(\star\).

2. Toán tử \(\setminus\) với \(x \setminus y = z\) tương đương với \(y = x \star z\).

3. Toán tử đối của \(\setminus\).

4. Toán tử \(/\).

5. Toán tử đối của \(/\).

Như vậy có tất cả sáu toán tử quasigroup và ta gọi tập các toán tử đó là parastrophe (hay conjugation, парастрофия).

Định nghĩa 1.34 (Loop)

Loop (hay лупа) là quasigroup \((Q, \star)\) với phần tử đơn vị \(e\) sao cho với mọi \(x \in Q\) thì

\[e \star x = x \star e = x.\]

Khi đó mỗi phần tử trong quasigroup sẽ có phần tử nghịch đảo (inverse) trái và phải tương ứng. Lưu ý rằng hai nghịch đảo không nhất thiết phải bằng nhau.

Định nghĩa 1.35 (Nhóm nhân)

Ta định nghĩa phép nhân (toán tử nhân)

\[\begin{split}L_x : Q \to Q, \quad L_x(y) = x \star y, \\ R_x : Q \to Q, \quad R_x(y) = y \star x.\end{split}\]

Đặt

\[\mathrm{mult}(Q) = \langle L_q, R_q : q \in Q \rangle.\]

Ta nói \(\mathrm{mult}(Q)\) là nhóm nhân của quasigroup (hay группа умножений квазигруппы).

Định nghĩa 1.36 (Chỉ số kết hợp)

Ta gọi bộ ba kết hợp (hay ассоциативная тройка) là ba phần tử \(a, b, c \in Q\) sao cho

\[a \star (b \star c) = (a \star b) \star c,\]

hay tương đương với

\[R_c(L_a(b)) = L_a(R_c(b)).\]

Khi đó chỉ số kết hợp (hay индекс ассоциативности) là số lượng bộ ba kết hợp trong quasigroup.

Nhận xét 1.8

Mục tiêu của quasigroup trong mật mã học là làm yếu tính kết hợp xuống. Như vậy nếu quasigroup có càng nhiều bộ ba kết hợp thì càng dễ bị tấn công hơn.

Nhận xét 1.9

Số lượng bộ ba kết hợp của quasigroup với order \(n\) thì không nhỏ hơn \(n\).

[TODO] Chứng minh tính chất này.