Tôi đã thấy rằng đôi khi người ta có thể sử dụng $B=HNF(G)$, nhưng nó có thể không phải lúc nào cũng hoạt động để có được một cơ sở xấu, và do đó nó không rõ ràng (cũng không rõ ràng đối với tôi ...).
Để cho $\mu : \mathbb{R}^{n\times n}\to \mathbb{R}_{\geq 0}$ là thước đo chất lượng của một cơ sở.
Ví dụ, một người có thể có $\mu(B) = \lVert LLL(B)_1\rVert$ là định mức của tọa độ đầu tiên của việc giảm LLL của $B$ (như bạn đề xuất), nhưng có thể có nhiều thước đo chất lượng khác.
Mục đích của việc sử dụng HNF không phải là nó dẫn đến một cơ sở "tồi tệ nhất" một cách trừu tượng (đối với hầu hết các phép đo chất lượng, nhân với một ma trận không mô đun ngẫu nhiên của định mức toán tử cao sẽ có thể dẫn đến một cơ sở chất lượng rất thấp), mà là rằng đó là điều tồi tệ nhất mà bất kỳ đối thủ nào cũng sẽ sử dụng hợp lý.
Điều này là do kết quả đơn giản sau đây.
Để cho $\mu$ có thể tính toán một cách hiệu quả.
Để cho $A$ là một đối thủ hiệu quả, trên đầu vào $B$, tính toán một số $U$ như vậy mà $\mu(BU) \leq f(B)$ cho một số chức năng giới hạn $f$. Sau đó, tồn tại một đối thủ hiệu quả $A'$ tính toán đó $U$ như vậy mà $\mu(BU) \leq \min(f(B), f(HNF(B))$.
Đáng chú ý, $HNF(B)$ là một bất biến của mạng tinh thểvà không phải là cơ sở cụ thể được sử dụng.
Do đó, kết quả trên nói rằng cơ sở chất lượng tồi tệ nhất mà đối thủ có thể tìm thấy nhiều nhất là $f(HNF(B))$, do đó, việc cung cấp cho đối thủ cơ sở không phải HNF có thể chỉ dẫn đến việc họ tính toán tốt hơn cơ sở chất lượng cao hơn so với cơ sở HNF.
kẻ thù $A'$ rất dễ để mô tả.
Nó chỉ đơn giản là chạy $A$ trên $B$ và $HNF(B)$và trả về cơ sở (trong số hai) giảm thiểu thước đo chất lượng.
Điều này không yêu cầu thước đo chất lượng phải được tính toán hiệu quả, nhưng trong hầu hết các trường hợp, điều này là đúng.
Chỉnh sửa: Để đáp lại sự làm rõ của bạn trong các nhận xét, tôi sẽ chỉ cho bạn một phần câu trả lời, đó là "về nguyên tắc là có, nhưng tôi không có sẵn ma trận rõ ràng".
Sau đây là từ Chương 3 của Luận văn của Seungki Kim.
Định lý 3.4 Để cho $n$ đủ lớn, $p\in (0,100)$, và giả sử $k < \frac{n}{6(\log n + K(p))}$ là một số nguyên dương, trong đó $K(p)$ là hằng số chỉ phụ thuộc vào $p$. Sau đó ít nhất $p\%$ của $n$-chiều $(1, 1/2)$-ĐLLL căn cứ có
$$\forall 1\leq i \leq n-1 : \frac{k-1}{k}\frac{1}{2}\leq |\mu_{i+1,i}|\leq \frac{ 1}{2}.$$
Ở đây "hầu hết" đòi hỏi sự chăm sóc kỹ thuật để có được quyền (xem luận điểm của Kim để biết chi tiết).
Kim tiếp tục thảo luận về kết quả này như thế nào là phản trực giác, theo nghĩa nó ngụ ý rằng đối với "hầu hết các cơ sở LLL $B$", $\lVert LLL(B)_1\rVert \approx (4/3)^{n/4}\approx (1,0745)^n$, trường hợp xấu nhất bị ràng buộc đối với LLL.
Nhưng nó là Mà còn được biết rằng, đối với hầu hết các bản phân phối trên các cơ sở mạng $B$, $\lVert LLL(B)_1\rVert \khoảng 1,02^n$ --- đưa cái gì?
Yêu cầu bồi thường là $LLL$ bằng cách nào đó thành kiến, theo nghĩa là nó làm không phải vận chuyển các phân phối đã nói ở trên qua các cơ sở mạng sang phân phối đồng đều trên các cơ sở LLL.
Do đó, để tìm các cơ sở LLL xấu, nên (trực tiếp) lấy mẫu các ma trận thỏa mãn điều kiện LLL (thay vì cố gắng sử dụng LLL để tính toán các cơ sở theo thực nghiệm).
Tôi đã không nghĩ liệu cách tự nhiên để làm điều này (mỗi lần một vectơ, ngẫu nhiên thống nhất từ một tập hợp phù hợp, với điều kiện bảo toàn điều kiện LLL) sẽ mang lại kết quả mong muốn.
Có thể có một cách thông minh hơn để lấy mẫu thống nhất một cơ sở LLL (theo kết quả của Kim, có thể là một cơ sở tồi).
Nhưng, theo luận điểm của Kim, đó là một điều hợp lý để cố gắng thực hiện.
Điều đáng nói là kết quả của Kim (ở mức tối thiểu) là một kết quả tồn tại.
Có vẻ hợp lý, lý do LLL hoạt động tốt ở mức trung bình là do giới hạn trường hợp xấu nhất lỏng lẻo.
Công việc của Kim cho thấy điều này không đúng.
