..

Sage and Lattice-based Cryptography

Trong bài viết này mình sẽ tóm tắt lại một số khái niệm cơ bản về đại số tuyến tính và lattice.

Không gian Vector

Khái niệm không gian vector là một trong những trụ cột quan trọng của bộ môn đại số tuyến tính. Việc hiểu rõ bản chất của không gian vector giúp ta xây dựng một nền tảng vững chắc phục vụ cho việc tiếp cận các khái niệm cao cấp hơn sau này. Trong bài viết này tác giả sẽ trình bày vắn tắt lại một số kết quả quan trọng liên quan đến không gian vector.

Định nghĩa 1. Không gian vector

Tập hợp $\displaystyle V$ được gọi là một không gian vector trên $\displaystyle \text{K}$ nếu nó được trang bị hai phép toán, phép toán đầu tiên là phép cộng hai vector, kí hiệu là $\displaystyle +$, phép toán thứ hai là phép nhân một vector với vô hướng $\displaystyle a$, kí hiệu là $\displaystyle \times$. Cụ thể, như sau

  • Phép cộng hai vector : là một ánh xạ $\displaystyle +:V\times V\rightarrow V$ , ví dụ $\displaystyle ( \alpha ,\beta )\rightarrow \alpha +\beta$
  • Phép nhân hai vector: là một ánh xạ $\displaystyle \times :\text{K} \times V\rightarrow V$ , ví dụ : $\displaystyle ( a,\alpha )\rightarrow a\alpha$ với $\displaystyle a\in \text{K} ,\alpha \in V$

Ngoài ra $\displaystyle V$ cũng thỏa mãn tính chất là một nhóm Abel đối với phép cộng và các mệnh đề về phân phối, giao hoán tương tự như khi làm việc trên tập số thực. Ở đây ta gọi các phần tử của $\displaystyle V$ là các vector còn các phần tử của $\displaystyle \text{K}$ là các vô hướng.

Độc lập tuyến tính và phụ thuộc tuyến tính

Định nghĩa 2. Tổ hợp tuyến tính, biểu thị tuyến tính

  • Một tổ hợp tuyến tính của các vector $\displaystyle \alpha _{1} ,\alpha _{2} ,…,\alpha _{n} \in V$ là một biểu thức có dạng
$ \sum _{i=1}^{n} a_{i} \alpha _{i} =a_{1} \alpha _{1} +...+a_{n} \alpha _{n} $

trong đó $\displaystyle a_{i} \in \text{K}$ là các vô hướng.

  • Giả sử $\displaystyle \alpha =a_{1} \alpha_{1} +…+a_{n} \alpha_{n}$ thì ta nói rằng vector $\displaystyle \alpha$ biểu thị tuyến tính được qua hệ các vector $\displaystyle \alpha _{1} ,…,\alpha _{n}$.

Ngoài ra một vector có thể có nhiều biểu thị tuyến tính khác nhau qua các hệ vector phân biệt. Biểu thị tuyến tính cũng có tính chất bắc cầu, tức là với hệ vector $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$, ta nói hệ biểu diễn được qua hệ vector $\displaystyle ( \beta _{1} ,…,\beta _{m})$ nếu như mỗi vector trong hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$ đều biểu thị tuyến tính được qua hệ $\displaystyle ( \beta _{1} ,…,\beta _{m})$, và tương tự nếu hệ $\displaystyle ( \beta _{1} ,…,\beta _{m})$ biểu thị tuyến tính được qua hệ $\displaystyle ( \gamma _{1} ,…,\gamma _{k})$ thì khi đó hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$ biểu thị tuyến tính được qua hệ $\displaystyle ( \gamma _{1} ,…,\gamma _{k})$.

Định nghĩa 3. Độc lập tuyến tính và phụ thuộc tuyến tính.

Hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$ được gọi là độc lập tuyến tính nếu hệ thức

$ a_{1} \alpha_{1} +...+a_{n} \alpha_{n} =0 $

xảy ra khi và chỉ khi $\displaystyle a_{1} =…=a_{n} =0$

Ngược lại hệ $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ được gọi là phụ thuộc tuyến tính nếu hệ thức trên xảy ra và có ít nhất một giá trị $\displaystyle a_{i} \neq 0$

Cơ sở và số chiều của không gian vector

Định nghĩa 4. Hệ sinh và cơ sở

a/ Một hệ vector của $\displaystyle V$ được gọi là một hệ sinh của $\displaystyle V$ nếu mọi vector của $\displaystyle V$ đều biểu thị tuyến tính được qua hệ đó.

b/ Một hệ vector của $\displaystyle V$ được gọi là một cơ sở của $\displaystyle V$ nếu mọi vector của $\displaystyle V$ đều được biểu thị tuyến tính một cách duy nhất qua hệ đó.

Từ đây ta có các khẳng định sau về hệ sinh và cơ sở là tương đương nhau

i/ $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ là một cơ sở của $\displaystyle V$

ii/ $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ là một hệ sinh độc lập tuyến tính của $\displaystyle V$

iii/ $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ là một hệ vector độc lập tuyến tính cực đại của $\displaystyle V$.

Chứng minh đơn giản như sau:

Từ i/ suy ra ii/ : $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ là một cơ sở của $\displaystyle V$. Với ràng buộc tuyến tính $\displaystyle 0=0\alpha_{1} +…+0\alpha_{n}$ thì vì $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ là một cơ sở của $\displaystyle V$ nên biểu diễn trên là duy nhất kéo theo $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ là một hệ sinh độc lập tuyến tính của $\displaystyle V$

Từ ii/ suy ra iii/ : $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ là một hệ sinh độc lập tuyến tính đồng nghĩa với việc mọi vector trong $\displaystyle V$ đều được biểu thị tuyến tính qua hệ và nó cũng là một hệ vector độc lập tuyến tính cực đại vì với $\displaystyle \beta \in V$ bất kì thì $\displaystyle \beta$ biểu thị tuyến tính được qua $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ cho nên $\displaystyle ( \alpha_{1} ,…,\alpha_{n} ,\beta )$ không còn độc lập tuyến tính

Từ iii/ qua i/ : Một hệ vector độc lập tuyến tính cực đại trong $\displaystyle V$ thì với mọi vector $\displaystyle \beta$ khác thuộc $\displaystyle V$ đều phải được biểu thị tuyến tính qua hệ này, có nghĩa là hệ này sinh ra $\displaystyle V$ và biểu diễn này là duy nhất. Vì giả sử rằng có hai biểu diễn là khác nhau tức là có ít nhất hai hệ số khác nhau giữa hai biểu diễn. Nếu lấy hiệu thì hệ không còn độc lập tuyến tính sinh ra mâu thuẫn.

Định nghĩa 5. Hữu hạn sinh

  • Một không gian vector được gọi là hữu hạn sinh nếu như nó có một hệ sinh gồm hữu hạn phần tử.

Định nghĩa 6. Chiều của không gian

  • Số phần tử của mỗi cơ sở của $\displaystyle K$-không gian vector hữu hạn sinh $\displaystyle V\neq {0}$ được gọi là số chiều của $\displaystyle V$ trên trường $\displaystyle K$. Kí hiệu là $\displaystyle \dim V$. Quy ước $\displaystyle \dim V=0$ khi $\displaystyle V={0}$.

Định lí. Giả sử $\displaystyle V\neq {0}$ là một không gian vector hữu hạn sinh. Khi đó, $\displaystyle V$ có một cơ sở gồm hữu hạn phần tử. Hơn nữa, mọi cơ sở của $\displaystyle V$ đều có số phần tử bằng nhau.

Chứng minh.

Trước hết ta có một bổ đề sau: Trong không gian vector $\displaystyle V$, giả sử hệ vector $\displaystyle ( \alpha_{1} ,…,\alpha_{r})$ độc lập tuyến tính và biểu thị tuyến tính được qua hệ $\displaystyle ( \beta_{1} ,…,\beta_{s})$ thì ta có $\displaystyle r\leqslant s$.

Ta chứng minh bổ đề trên như sau: Theo giả thiết ta có một biểu thị tuyến tính như sau

$ \alpha_{1} =a_{1} \beta_{1} +...+\beta_{s} $

Vì hệ $\displaystyle ( \alpha_{1} ,…,\alpha_{n})$ độc lập tuyến tính cho nên ta có thể giả sử $\displaystyle \alpha_{1} \neq 0$ và giả sử không mất tính tổng quát rằng $\displaystyle a_{1} \neq 0$. Khi đó $\displaystyle \beta_{1}$ có một biểu thị tuyến tính như sau:

$ \alpha_{1} a_{1}^{-1} -\sum_{j=2}^{s} \beta_{j}\left( a_{j} a_{1}^{-1}\right) =\beta_{1} $

Như vậy $\displaystyle \beta _{1}$ biểu thị tuyến tính được qua hệ $\displaystyle ( \alpha _{1} ,\beta _{2} ,…,\beta _{s})$,và khi đó $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ biểu thị tuyến tính qua $\displaystyle ( \beta _{1} ,…,\beta _{s})$ còn $\displaystyle ( \beta _{1} ,…,\beta _{s})$ lại biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,…,\beta _{s})$ cho nên $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,…,\beta _{s})$. Lí do có biểu diễn trên là vì: ta đã có $\displaystyle \beta _{1}$ biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,…,\beta _{s})$. Tương tự với $\displaystyle \beta _{2}$ cũng biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,\beta _{2} ,…,\beta _{s})$ bằng cách lấy mọi vô hướng của các số $\displaystyle \alpha _{1} ,\beta _{i} ,i\neq 2$ đều bằng không thì ta có được một biểu thị tuyến tính.

Bây giờ tiếp tục ta sẽ chứng minh được rằng $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,..,\alpha _{i} ,\beta _{i+1} ,…,\beta _{s})$ trong đó $\displaystyle i\leqslant \min{r,s}$. Ta sẽ quy nạp. Đầu tiên với $\displaystyle i=1$ thì mệnh đề đúng theo điều vừa chỉ ra ở trên. Giả sử nó đúng tới $\displaystyle i$ và ta sẽ chứng minh $\displaystyle i+1$ cũng đúng trong trường hợp $\displaystyle i+1\leqslant \min\lbrace r,s\rbrace$.

Ta có $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,…,\alpha _{i} ,\beta _{i+1} ,…,\beta _{s})$. Như vậy $\displaystyle \alpha _{i+1}$ biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,…,\alpha _{i} ,\beta _{i+1} ,…,\beta _{s})$ cho nên ta có

$ \alpha _{i+1} =\sum _{j=1}^{i} \gamma _{j}^{( i+1)} \alpha _{j} +\sum _{j=i+1}^{s} \lambda _{j}^{( i+1)} \beta _{j} $

Ta có hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ là một hệ độc lập tuyến tính cho nên khi đó có ít nhất một giá trị $\displaystyle \lambda _{j}^{i+1} \neq 0$ vì nếu không thì $\displaystyle \alpha _{i+1}$ biểu thị tuyến tính qua $\displaystyle ( \alpha _{1} ,…,\alpha _{i} ,…,\alpha _{r})$ là mẫu thuẫn vì $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ là một hệ độc lập tuyến tính. Tương tự như trên ta cũng suy ra $\displaystyle \beta _{i+1}$ biểu thị tuyến tính được qua hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{i} ,\alpha _{i+1} ,\beta _{i+2} ,…,\beta _{s})$. Cho nên $\displaystyle (\alpha _{1} ,..,\alpha _{i} ,\beta _{i+1} ,…,\beta _{s})$ biểu thị tuyến tính qua hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{i} ,\alpha _{i+1} ,\beta _{i+2} ,…,\beta _{s})$. Suy ra ta có điều phải chứng minh. Bây giờ nếu $\displaystyle r >s$ thì ta suy ra $\displaystyle i=s$. Khi đó $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ biểu thị tuyến tính qua hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{s})$ là mâu thuẫn với giả sử hệ độc lập tuyến tính. Vậy $\displaystyle r\leqslant s$.

Bây giờ ta sẽ quay trở lại chứng minh định lí ban đầu.

Giả sử $\displaystyle ( \gamma _{1} ,…,\gamma _{s})$ là một hệ sinh hữu hạn của $\displaystyle V$. Ta gọi $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ là một hệ độc lập tuyến tính trong $\displaystyle V$. Hệ này biểu thị tuyến tính được qua $\displaystyle ( \gamma _{1} ,…,\gamma _{s})$ theo định nghĩa của hệ sinh. Suy ra theo bổ đề thì $\displaystyle r\leqslant s$. Ta tiếp tục bổ sung vào trong hệ $\displaystyle ( \alpha _{1} ,…,\alpha _{r})$ các vector để sao cho hệ vẫn là hệ độc lập tuyến tính và rõ ràng, quá trình này phải dừng lại sau hữu hạn bước và hệ thu được là hệ vector độc lập tuyến tính cực đại trong $\displaystyle V$. Vì là hệ vector độc lập tuyến tính cực đại nên mỗi vector trong $\displaystyle V$ được biểu thị duy nhất qua hệ này. Suy ra ta có điều phải chứng minh.

Cuối cùng là một định lí, có thể coi như là hệ quả của kết quả trên.

Định lí. Giả sử $\displaystyle V$ là một không gian vector hữu hạn sinh. Khi đó mọi hệ sinh của $\displaystyle V$ đều chứa một cơ sở. Mọi hệ độc lập tuyến tính trong $\displaystyle V$ đều có thể được bổ sung để trở thành một cơ sở của $\displaystyle V$. Nếu $\displaystyle \dim V=n$, thì mọi hệ độc lập tuyến tính gồm $\displaystyle n$ vector của $\displaystyle V$ đều là một cơ sở.

Ngoài ra người ta cũng nhận xét được rằng, trong một không gian vector vô hạn sinh (tức là không hữu hạn sinh), hai cơ sở bất kì đều có cùng lực lượng. Nhưng một hệ vector độc lập tuyến tính có cùng lực lượng với cơ sở thì không nhất thiết là một cơ sở.

Định nghĩa 7. Tọa độ

Bộ vô hướng $\displaystyle ( a_{1} ,…,a_{n})$ xác định bởi điều kiện $\displaystyle \alpha =\sum_{i=1}^{n} a_{i} \alpha_{i}$ được gọi là tọa độ của vector $\displaystyle \alpha$ trong cơ sở $\displaystyle ( \alpha_{1} ,\alpha_{2} ,…,\alpha_{n})$. Vô hướng $\displaystyle a_{i}$ được gọi là tọa độ thứ $\displaystyle i$ của $\displaystyle \alpha$ trong cơ sở đó.

Bây giờ ta cùng xem xét tọa độ của một vector trong những cơ sở khác nhau thì có liên quan với nhau như thế nào. Xét hai cơ sở $\displaystyle ( \beta _{1} ,…,\beta _{n})$ và $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$ của không gian vector $\displaystyle V$. Như vậy mỗi vector $\displaystyle \beta _{i}$ biểu thị tuyến tính được qua $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$ tức là có các số $\displaystyle \gamma _{i}^{( j)}$ sao cho

$ \displaystyle \beta _{j} =\sum _{i=1}^{n} \gamma _{i}^{( j)} \alpha _{i} $

Giả sử $\displaystyle \alpha$ có tọa độ lần lượt là $\displaystyle ( a_{1} ,…,a_{n})$ và $\displaystyle ( b_{1} ,…,b_{n})$ trong hai cơ sở $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$ và $\displaystyle ( \beta _{1} ,…,\beta _{n})$. Thì khi đó

$ \displaystyle \alpha =\sum_{j=1}^{n} b_{j} \beta_{j} =\sum_{j=1}^{n} b_{j}\sum_{i=1}^{n} \gamma _{i}^{( j)} \alpha _{i} =\sum_{j=1}^{n}\left(\sum_{i=1}^{n} b_{j} \gamma _{i}^{( j)}\right) \alpha _{i} =\sum_{j=1}^{n} a_{j} \alpha _{j} $

Và do mỗi biểu thị tuyến tính của $\displaystyle \alpha$ trong $\displaystyle ( \alpha _{1} ,…,\alpha _{n})$ là duy nhất cho nên ta có

$ \displaystyle a_{j} =\sum _{i=1}^{n} b_{j} \gamma _{i}^{( j)} ,j=1,2,...,n $

Không gian con - Hạng của một hệ vector

Định nghĩa 8. Không gian con

Tập con không rỗng $\displaystyle W\subset V$ được gọi là một không gian vector con của $\displaystyle V$ nếu như $\displaystyle W$ cũng đóng kín đối với hai phép toán trên $\displaystyle V$, tức là

$ \alpha +\beta \in W,\forall \alpha ,\beta \in W $
$ a\alpha \in W,\forall a\in \text{K} ,\alpha \in W $

Mệnh đề 1. Nếu $\displaystyle W$ là một không gian vector con của $\displaystyle V$ thì ta cũng có $\displaystyle \dim W\leqslant \dim V$.

Kết quả trên là hệ quả trực tiếp của khái niệm về số chiều của một không gian vector. Cụ thể với mỗi hệ độc lập tuyến tính trong $\displaystyle W$ thì cũng độc lập tuyến tính trong $\displaystyle V$. Ngoài ra mỗi phần tử của hệ độc lập tuyến tính đều được biểu thị tuyến tính thông qua cơ sở của $\displaystyle V$ cho nên ta có $\displaystyle \dim W\leqslant \dim V$. Dấu bằng xảy ra khi và chỉ khi $\displaystyle \dim W=\dim V=n$ hay $\displaystyle W=V$, tức là khi đó mọi cơ sở của $\displaystyle W$ cũng là cơ sở của $\displaystyle V$

Mệnh đề 2. Giao của một họ bất kì các không gian vector con của $\displaystyle V$ cũng là một không gian vector con của $\displaystyle V$.

Thật vậy, xét một họ các không gian vector con của $\displaystyle V$ là $\displaystyle \lbrace V_{i}\rbrace_{i\in I}$ thì khi đó $\displaystyle \cap_{i\in I} V_{i}$ cũng thỏa mãn tính đóng đối với phép cộng và nhân.

Định nghĩa 9. Không gian vector sinh bởi $X$

Giả sử $\displaystyle X$ là một tập con của không gian vector $\displaystyle V$. Giao của tất cả các không gian vector con của $\displaystyle V$ mà chứa $\displaystyle X$ được gọi là không gian vector con của $\displaystyle V$ sinh bởi $\displaystyle X$ và được kí hiệu là $\displaystyle \mathcal{L}( X)$.

Từ định nghĩa, ta suy ra được rằng $\displaystyle \mathcal{L}( X)$ là không gian vector con nhỏ nhất của $\displaystyle V$ mà chứa $\displaystyle X$

Khi đó $\displaystyle \mathcal{L}( X)$ là tập hợp các tổ hợp tuyến tính của các phần tử của $\displaystyle X$. Nói riêng nếu $\displaystyle X=\lbrace \gamma _{1} ,…,\gamma _{k}\rbrace $ thì

$ \displaystyle \mathcal{L}( X) =\left\{\sum _{i=1}^{k} a_{i} \gamma _{i} |a_{i} \in \text{K}\right\} $

Thật vậy, tập hợp các tổ hợp tuyến tính của $\displaystyle X$ chính là một không gian con của $\displaystyle V$ mà chứa $\displaystyle X$. Mặt khác, mọi tổ hợp tuyến tính của $\displaystyle X$ đều nằm trong mọi không gian vector con của $\displaystyle V$ mà chứa $\displaystyle X$. Vì với mỗi không gian vector con $\displaystyle W\subset V$ mà $\displaystyle W$ chứa $\displaystyle X$ thì khi đó các phần tử của $\displaystyle X$ cũng thỏa mãn tính đóng đối với phép cộng và nhân vô hướng trên $\displaystyle W$. Điều này dẫn tới mọi tổ hợp tuyến tính của $\displaystyle X$ cũng nằm trong $\displaystyle W$.

Tiếp theo ta xét về số chiều của $\displaystyle \mathcal{L}( X)$.

Nhận xét: Số chiều của không gian $\displaystyle \mathcal{L}( X)$ được gọi là hạng của tập hoặc hệ vector $\displaystyle X$ và được kí hiệu là $\displaystyle \text{rank}( X)$. Tương tự ta gọi một tập con các vector của $\displaystyle X$ là tuyến tính cực đại nếu như ta thêm bất kì vector nào trong $\displaystyle X$ vào tập đó thì tập sẽ trở thành tập con phụ thuộc tuyến tính. Như vậy, để tính hạng của $\displaystyle \mathcal{L}( X)$ ta sẽ đếm số vector của mỗi tập con độc lập tuyến tính cực đại trong $\displaystyle X$.

Hệ quả: Hai tập con độc lập tuyến tính cực đại trong $\displaystyle \mathcal{L}( X)$ thì có số phần tử bằng nhau.

Tổng và tổng trực tiếp

Ta giả sử $\displaystyle W_{1} ,…,W_{n}$ là các không gian vector con của $\displaystyle V$. Khi đó tập hợp

$ W_{1} +...+W_{n} =\{\alpha _{1} +...+\alpha _{n} |\alpha _{i} \in W_{i} ,i=1,..,n\} $

hiển nhiên lập nên một không gian vector con của $\displaystyle V$.

Định nghĩa 10. Tổng của các không gian vector

Không gian vector $\displaystyle \sum_{i=1}^{n} W_{i}$ được gọi là tổng của các không gian vector con $\displaystyle W_{1} ,…,W_{n}$.

Khi đó mỗi vector $\displaystyle \alpha$ thuộc không gian vector trên có thể được viết dưới dạng

$ \alpha =\alpha _{1} +...+\alpha _{n} ,\alpha _{i} \in W_{i} $

Tuy vậy, cách viết trên không phải là duy nhất. Vì thế ta đi đến một khái niệm chặt hơn như sau.

Định nghĩa 11. Tổng trực tiếp

Nếu mọi vector trong không gian $\displaystyle \sum_{i=1}^{n} W_{i}$ đều được viết duy nhất dưới dạng $\displaystyle \alpha =\alpha_{1} +…+\alpha_{n}$ thì khi đó ta gọi $\displaystyle \sum_{i=1}^{n} W_{i}$ là tổng trực tiếp của các không gian vector $\displaystyle W_{i}$ và kí hiệu là $\displaystyle W_{1} \oplus …\oplus W_{n}$. Từ định nghĩa trên ta đi đến các tính chất nhằm giúp ta xác định khi nào tổng trên thỏa mãn là một tổng trực tiếp của các không gian vector con.

Định lí. $\displaystyle \sum_{i=1}^{n} W_{i}$ là tổng trực tiếp khi và chỉ khi điều kiện sau đây được thỏa mãn:

$ \displaystyle W_{i} \cap \left(\sum _{j\neq i} W_{j}\right) =\{0\} ,i=1,2,...,n $

Ta có định lí sau đây khi nói về số chiều của tổng các không gian vector:

Định lí. Giả sử $\displaystyle U$ và $\displaystyle W$ là một không gian vector con của một không gian vector $\displaystyle V$ hữu hạn chiều. Khi đó ta có

$ \dim U+\dim W=\dim( U+W) +\dim( U\cap W) $

Định nghĩa 12. Phần bù tuyến tính

Nếu $\displaystyle V=U\oplus W$ thì $\displaystyle W$ được gọi là một phần bù tuyến tính của $\displaystyle U$ trong $\displaystyle V$ và $\displaystyle \dim W=\dim V-\dim U$ được gọi là đối chiều của $\displaystyle U$ trong $\displaystyle V$. Giả sử $\displaystyle V=U\oplus W$. Khi đó mỗi vector trong $\displaystyle v$ có thể được biểu diễn duy nhất dưới $\displaystyle v=u+w$.

Định nghĩa một ánh xạ

$ pr_{U} :V\rightarrow U $
$ pr_{U}( v) =u $

Nó được gọi là phép chiếu từ $\displaystyle V$ lên $\displaystyle U$ theo phương $\displaystyle W$. Phép chiếu có các tính chất sau:

$ pr_{U}( v+v') =pr_{U}( v) +pr_{U}( v') ,\forall v,v'\in V $
$ pr_{U}( av) =apr_{U}( v) ,\forall v\in V $

Lattice

Phần này mình sẽ không đi sâu vào các thuật toán mà chỉ trình bày lại các khái niệm quan trọng về Lattice

Qui ước

Các kí hiệu: Các vector với các phần tử trong $\displaystyle \mathbb{R}$ được xem như là vector cột và được biểu thị bằng các chữ in thường đậm, ví dụ $\displaystyle \mathbf{x} ,\mathbf{y} ,\mathbf{z}$. Các ma trận được biểu thị bằng các chữ cái in hoa đậm, ví dụ $\displaystyle \mathbf{A} ,\mathbf{S} ,\mathbf{B} ,…$

Chuyển vị của một vector hoặc ma trận được biểu thị bằng $\displaystyle \mathbf{v}^{T}$ hoặc $\displaystyle \mathbf{V}^{T}$ tương ứng. Ngoài ra, chúng ta biểu thị tích trong của hai vector cột $\displaystyle \mathbf{v} ,\mathbf{w} \in \mathbb{R}^{n}$ theo $\displaystyle \langle \mathbf{v} ,\mathbf{w} \rangle =\mathbf{v}^{T}\mathbf{w}$.

Một số kí hiệu khác:

  • $\displaystyle \mathbb{R}^{n\times m}$: không gian của ma trận $\displaystyle n\times m$ với các mục số thực
  • $\displaystyle | \cdotp | ,\ | \cdotp | _{\infty }$: Chuẩn Euclid và chuẩn tối đa
  • $\displaystyle \mathcal{L}$: Một lưới
  • $\displaystyle \mathcal{L}(\mathbf{B})$: lưới với các cột của ma trận $\displaystyle \mathbf{B}$ làm cơ sở.
  • $\displaystyle \lambda _{i}(\mathcal{L})$: Số nhỏ nhất sao cho có $\displaystyle i$ vector độc lập tuyến tính trong $\displaystyle \mathcal{L}$ mà mỗi vector đó có chuẩn không vượt quá $\displaystyle \lambda _{i}$.
  • $\displaystyle \gamma$ : Hệ số xấp xỉ (gần đúng) trong các bài toán lưới
  • $\displaystyle \mathbf{b}_{i}$: một vector cơ sở lưới
  • $\displaystyle \mathbf{b}_{i}^{*}$: một vector trong cơ sở trực giao Gram-Schmidt của một lưới.

Nhắc lại một số định nghĩa

Một lattice ${\displaystyle \mathcal{L} \subset \mathbb{R}^{m}}$ là tập hợp các tổ hợp tuyến tính nguyên của các vector độc lập tuyến tính. Tức là

$ \displaystyle \mathcal{L} =\left\{\sum _{i=1}^{n} x_{i}\mathbf{b}_{i} \ \middle| x_{i} \in \mathbb{Z}\right\} $

trong đó $\displaystyle \lbrace \mathbf{b}_{i}\rbrace _{i=1}^{n} \subset \mathbb{R}^{m}$. Đặt $\displaystyle \mathbf{B} \in \mathbb{R}^{m\times n}$ thì $\displaystyle \mathcal{L} =\mathbf{B}\mathbb{Z}^{n}$, đồng nghĩa với việc $\displaystyle \mathcal{L}$ là ảnh của $\displaystyle \mathbb{Z}^{n}$ dưới ánh xạ tuyến tính $\displaystyle \mathbf{B} :\mathbb{R}^{n}\rightarrow \mathbb{R}^{m}$.

Ta có thể định nghĩa lưới theo một cách khác. Cho $\displaystyle m,n,k\in \mathbb{Z}_{ >0}$ với $\displaystyle m\geqslant k$.

Một lưới $\displaystyle m$ chiều $\displaystyle \mathcal{L}$ là một nhóm con cộng rời rạc của $\displaystyle \mathbb{R}^{m}$ chứa tất cả các tổ hợp tuyến tính nguyên của $\displaystyle k$ vector độc lập tuyến tính $\lbrace \mathbf{b_1}, \mathbf{b_2}, \ldots, \mathbf{b_k} \rbrace$. Đó là $\displaystyle \mathcal{L} =\lbrace \mathbf{Bx} \mid \mathbf{x} \in \mathbb{Z}^{k}\rbrace$ với ma trận $\displaystyle \mathbf{B} =(\mathbf{b_1} ,…,\mathbf{b_k}) \in \mathbb{R}^{m\times k}$.

Ta gọi $\displaystyle \mathbf{B}$ là cơ sở của $\displaystyle \mathcal{L}$ và $\displaystyle k$ là rank của lưới. Sau này ta chỉ quan tâm tới các full rank lattice tức là các lattice có hạng bằng với số chiều.

Định thức của một lưới $\displaystyle \mathcal{L}$ với cơ sở $\displaystyle \mathbf{B}$ được xác định bởi $\displaystyle \det(\mathcal{L}) =\sqrt{\mid \det\left(\mathbf{B}^{T}\mathbf{B}\right)\mid }$. Nếu lattice $\displaystyle \mathcal{L}$ là full rank thì $\displaystyle \det(\mathcal{L}) =\mid\det(\mathbf{B})\mid$.

Lưu ý rằng cơ sở của một lưới không là duy nhất, hay nói đúng hơn với mỗi ma trận đơn nhất $\displaystyle \mathbf{U} \in \mathbb{Z}^{n\times n}$ thì $\displaystyle \mathbf{BU}$ cũng là cơ sở cho cùng một lưới. Vì ta có tính chất sau: Với hai cơ sở $\displaystyle \mathbf{B}$ và $\displaystyle \mathbf{B} ‘$ cho lưới $\displaystyle \mathcal{L}$ thì $\displaystyle \mathcal{L}(\mathbf{B}) =\mathcal{L}(\mathbf{B} ‘)$ cho nên suy ra $\displaystyle \det(\mathbf{B}) =\det(\mathbf{B} ‘)$.

Một ma trận đơn nhất $\displaystyle \mathbf{U}$ là một ma trận thỏa mãn $\displaystyle \det(\mathbf{U}) =1$. Như vậy nếu ta lấy $\displaystyle \mathbf{B} ‘=\mathbf{BU}$ thì sẽ thỏa mãn định thức hai ma trận trên là như nhau.

Tính chất trên tuy đơn giản nhưng rất quan trọng đối với việc triển khai các hệ mật, vì một số cơ sở dễ xử lí hơn những cơ sở khác.

Mỗi lưới $\displaystyle \mathcal{L}$ có một lưới đối ngẫu (dual lattice), kí hiệu $\displaystyle \mathcal{L}^{*} =\lbrace \mathbf{w} \in \mathbb{R}^{m} \mid \langle \mathbf{w} ,\mathbf{x} \rangle \in \mathbb{Z} ,\forall \mathbf{x} \in \mathcal{L}\rbrace$.

Sage

Đối với lattice ta sẽ làm việc trên các ma trận hệ số nguyên hoặc hữu tỉ tùy vào trường hợp.

Trong Sagemath sẽ có 2 loại ma trận chính là Dense matrix và Sparse matrix. Điểm khác biệt giữa hai loại ma trận này là Dense matrix sẽ lưu trữ tất cả các phần tử của ma trận, trong khi Sparse matrix chỉ lưu trữ các phần tử khác không.

Ví dụ:

sage: import sys
sage: M = matrix(ZZ, [[1,0,0],[2,3,0],[0,0,0]], sparse = True)
sage: sys.getsizeof(M)
112
sage: N = M.dense_matrix()
sage: N.__sizeof__
<built-in method __sizeof__ of sage.matrix.matrix_integer_dense.Matrix_integer_dense object at 0x7fc00281d1b0>
sage: N.__sizeof__()
128
sage:

Để tạo một ma trận trong sage thì dùng cú pháp đơn giản sau:

Matrix = matrix(K,nrows,ncols, list of lists)

Chi tiết mọi người tham khảo doc ở dưới phần tài liệu tham khảo

Để tạo một vector space và lấy cơ sở của nó thì ta làm như sau:

sage: M = MatrixSpace(ZZ, 2, 3).basis()
sage: M
Finite family {(0, 0): [1 0 0]
[0 0 0], (0, 1): [0 1 0]
[0 0 0], (0, 2): [0 0 1]
[0 0 0], (1, 0): [0 0 0]
[1 0 0], (1, 1): [0 0 0]
[0 1 0], (1, 2): [0 0 0]
[0 0 1]}
sage: list(M)
[
[1 0 0]  [0 1 0]  [0 0 1]  [0 0 0]  [0 0 0]  [0 0 0]
[0 0 0], [0 0 0], [0 0 0], [1 0 0], [0 1 0], [0 0 1]
]
sage:

Ngoài ra trong Sage có cung cấp cho ta module IntegerLattice để làm việc với lattice.

sage: from sage.modules.free_module_integer import IntegerLattice
sage: A = random_matrix(ZZ, 80,80, x = -200, y = 200)
sage: A
80 x 80 dense matrix over Integer Ring (use the '.str()' method to see the entries)
sage: L = IntegerLattice(A)
sage: L.LLL()
80 x 80 dense matrix over Integer Ring (use the '.str()' method to see the entries)
sage: L.shortest_vector().norm().log(2).n()
9.85498530685853
sage: M = L.LLL(algorithm='flatter')
sage:

Bài viết xin tạm dừng tại đây. Trong các phần tiếp theo mình sẽ đi sâu vào một số thuật toán liên quan tới lattice cũng như các bài toán khó dựa trên lattice.

Tài liệu tham khảo

  • https://eprint.iacr.org/2023/032.pdf
  • https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html

  • https://doc.sagemath.org/html/en/reference/matrices/sage/matrix/constructor.html#sage.matrix.constructor.matrix

  • https://doc.sagemath.org/html/en/reference/modules/sage/modules/free_module_integer.html