Hàm Boolean và mật mã đối xứng¶
Giới thiệu hàm Boolean¶
Hàm đơn điệu¶
Định nghĩa 45 (Vector so sánh được)
Xét hai vector \(\bm{a} = (a_1, a_2, \ldots, a_n)\) và \(\bm{b} = (b_1, b_2, \ldots, b_n)\) với \(a_i, b_i \in \mathbb{F}_2\).
Ta nói \(\bm{a}\) so sánh được nhỏ hơn \(\bm{b}\) nếu với mọi \(i = 1, 2, \ldots, n\) ta có \(a_i \leqslant b_i\). Kí hiệu \(\bm{a} \preccurlyeq \bm{b}\).
Ví dụ 22
Ta có \((1, 0, 0) \preccurlyeq (1, 0, 1)\), còn \((1, 0, 0)\) và \((0, 1, 0)\) thì không so sánh được (vị trí thứ nhất và thứ hai).
Định nghĩa 46 (Hàm boolean đơn điệu)
Hàm boolean \(n\) biến \(f(x_1, x_2, \ldots, x_n)\) được gọi là hàm đơn điệu (hay monotone) nếu với mọi vector \((a_1, a_2, \ldots, a_n) \preccurlyeq (b_1, b_2, \ldots, b_n)\) thì ta có
Ví dụ 23
Xét hàm boolean \(f(x, y) = (0, 1, 0, 1)\).
Ta thấy rằng:
\((0, 0) \preccurlyeq (0, 1)\) và \(f(0, 0) = 0 \leqslant 1 = f(0, 1)\);
\((0, 0) \preccurlyeq (1, 0)\) và \(f(0, 0) = 0 \leqslant 0 = f(1, 0)\);
\((0, 0) \preccurlyeq (1, 1)\) và \(f(0, 0) = 0 \leqslant 1 = f(1, 1)\);
\((0, 1)\) và \((1, 0)\) không so sánh được nên bỏ qua;
\((0, 1) \preccurlyeq (1, 1)\) và \(f(0, 1) = 1 \leqslant 1 = f(1, 1)\);
\((1, 0) \preccurlyeq (1, 1)\) và \(f(1, 0) = 0 \leqslant 1 = f(1, 1)\).
Vậy đây là hàm đơn điệu.
Khoảng cách Hamming¶
Định nghĩa 47 (Khoảng cách Hamming giữa hai vector)
Với hai vector \(\bm{x}\), \(\bm{y}\) thuộc \(\mathbb{F}_2^n\), đặt
là khoảng cách Hamming giữa hai vector \(\bm{x}\) và \(\bm{y}\). Trong đó \(\mathrm{wt}(\bm{z})\) là trọng số vector \(\bm{z}\).
Định nghĩa 48 (Khoảng cách Hamming từ vector tới tập vector)
Xét \(M \subseteq \mathbb{F}_2^n\). Khi đó với mọi \(\bm{x} \in \mathbb{F}_2^n\), ta nói khoảng cách từ \(\bm{x}\) tới \(M\) là
Định nghĩa 49 (Khoảng cách Hamming giữa hai hàm boolean)
Xét hai hàm boolean \(n\) biến là \(f(x_1, x_2, \ldots, x_n)\) và \(g(x_1, x_2, \ldots, x_n)\). Khi đó khoảng cách Hamming từ hàm \(f\) tới hàm \(g\) là