Chapter 7. Lattices and Cryptography¶
Exercise (Câu 7.43)
Đáp án: \(t = \dfrac{\bm{b}_1 \cdot \bm{b}_2}{\lVert \bm{b}_1 \rVert^2}\) và \(\bm{b}_2^* = \bm{b}_2 - t \bm{b}_1\) nên suy ra
Do đó \(\bm{b}_2^* \perp \bm{b}_1\) và \(\bm{b}_2^*\) là hình chiếu của \(\bm{b}_2\) lên orthogonal complement của \(\bm{b}_1\).
Exercise (Câu 7.44)
Đáp án:
với mọi \(t \in \mathbb{R}\).
Cho \(\bm{a} - t \bm{b} = 0\) ta có \(t = \dfrac{\bm{a} \cdot \bm{b}}{\lVert \bm{b} \rVert^2}\).
Từ đó ta có
Vì vậy \(\bm{a} - t \bm{b}\) là hình chiếu của \(\bm{a}\) lên orthogonal complement của \(b\) (tương tự 7.43).
Exercise (Câu 7.45)
Đáp án ở dưới.
Thuật toán Gauss's lattice reduction.
Thuật toán 3 (Thuật toán Gauss's latice reduction)
While True
If \(\lVert \bm{v}_2 \rVert < \lVert \bm{v}_1 \rVert\)
swap \(\bm{v}_1\) and \(\bm{v}_2\)
\(m \gets \lfloor \bm{v}_1 \cdot \bm{v}_2 / \lVert \bm{v}_1 \rVert^2 \rceil\)
EndIf
If \(m = 0\)
return \((\bm{v}_1, \bm{v}_2)\)
EndIf
Replace \(\bm{v}_2\) with \(\bm{v}_2 - m\bm{v}_1\)
EndWhile
\(\bm{v}_1 = (14, -47)\), \(\bm{v}_2 = (-362, -131)\), 6 steps.
\(\bm{v}_1 = (14, -47)\), \(\bm{v}_2 = (-362, -131)\), 6 steps.
\(\bm{v}_1 = (147, 330)\), \(\bm{v}_2 = (690, -207)\), 7 steps.
Exercise (Câu 7.46)
Đáp án ở dưới.
Do \(W^\perp\) là orthogonal complement của \(W\) trong \(V\) nên nếu \(\bm{z} \in W^\perp\) thì \(\bm{z} \cdot \bm{y} = 0\), với mọi \(\bm{y} \in W\).
Với hai vector \(\bm{z}_1, \bm{z}_2 \in W^\perp\) ta có \(\bm{z}_1 \cdot \bm{y} = \bm{z}_2 \cdot \bm{y} = 0\), với mọi \(\bm{y} \in W\).
Như vậy \((\bm{z}_1 + \bm{z}_2) \cdot \bm{y} = 0 \Rightarrow \bm{z}_1 + \bm{z}_2 \in W^\perp\).
Ta lại có \(\alpha \bm{z}_1 \cdot \bm{y} = \alpha \cdot 0 = 0 \Rightarrow \alpha\bm{z}_1 \in W^\perp\) với mọi \(\alpha \in \mathbb{R}\).
Tới đây ta có hai cách giải.
Cách 1. Ta có \(W \cup W^\perp = \{\bm{0}\}\). Nếu \(\bm{u}\) thuộc cả hai tập \(W\) và \(W^\perp\) thì \(\bm{u} \cdot \bm{u} = 0 \Rightarrow \bm{u} = \bm{0}\).
Kí hiệu \(U = W + W^\perp\), ta chứng minh \(W = V\).
Ta có thể chọn một cơ sở trực chuẩn (orthonormal basis) trong \(U\) và mở rộng nó thành cơ sở trực chuẩn trong \(V\).
Khi đó, nếu \(U \neq V\) thì có một phần tử \(\bm{e}\) trong cơ sở của \(V\) vuông góc với \(U\). Do \(U\) chứa \(W\) và \(\bm{e}\) vuông góc với \(U\) nên \(\bm{e} \in W^\perp\).
Phần sau là không gian con của \(W\), do đó \(e\) thuộc \(W\), mâu thuẫn.
Cách 2. Đặt \(\{ \bm{e}_1, \bm{e}_2, \cdots, \bm{e}_k \}\) là cơ sở trực chuẩn của không gian con \(W\). Với mỗi \(\bm{v} \in V\), đặt
Khi đó với mọi \(\bm{v} \in V\) thì \(\bm{v} = \underbrace{P(\bm{v})}_{\in W} + \underbrace{(\bm{v} - P(\bm{v}))}_{\in W^\perp}\).
Ở đây \(\bm{v} - P(\bm{v}) \in W^\perp\) là vì nếu \(j \in \{ 1, 2, \cdots, k \}\) thì
Do \(\{ \bm{e}_1, \cdots, \bm{e}_k \}\) là cơ sở của \(W\), điều này cho ta \(\bm{v} - P(\bm{v}) \in W^\perp\).
Như vậy