Viết ra một câu trả lời để điều này không được trả lời, mặc dù HNF đã được đề cập trong các nhận xét.
Hermite Normal Form là cách tiêu chuẩn để giảm một bộ tạo thành cơ sở.
Điều này có nghĩa là đây là cách tiêu chuẩn để tính toán một số thao tác trên mạng (có thể dễ dàng biểu thị dưới dạng vectơ cơ sở), chẳng hạn
$L+L'$ (mà ví dụ của bạn là trường hợp đặc biệt), hoặc
$L\cap L'$ (điều này ít rõ ràng hơn và đòi hỏi tính hai mặt).
Xem các vấn đề mạng tinh thể dễ dàng của những ghi chú này.
Bạn đã nhận xét
Có vẻ như việc tính toán dạng chuẩn Hermite một cách hiệu quả là không hề nhỏ...
Điều này (gần như) đúng, nhưng không tầm thường còn lâu mới "khó".
Tôi trích dẫn từ các ghi chú
Không khó để đưa ra một thuật toán tính HNF của một ma trận chỉ thực hiện một số phép toán đa thức. Tuy nhiên, một giải pháp ngây thơ cho vấn đề này có thể dẫn đến thời gian chạy siêu đa thức vì các số trong phép tính trung gian có thể dễ dàng trở nên rất lớn.
Các ghi chú được liên kết bao gồm mã giả để triển khai HNF trong thời gian chạy đa thức (bằng cách đảm bảo các giá trị trung gian luôn được giới hạn).
Nó có lẽ phức tạp hơn một chút so với LLL, nhưng thực sự không nhiều --- cả hai đều là thuật toán mà tôi mong đợi một sinh viên năm cuối/sinh viên năm cuối có thể thực hiện mà không cần nỗ lực quá nhiều.
Tất nhiên, bạn có thể dành nhiều nỗ lực hơn để có được những thứ hiệu quả thực tế hơn.
Xem bài báo này của Pernet và Stein. Vì Stein là người sáng lập Sage CAS, tôi cho rằng điều này khá gần với những gì Sage đã triển khai, ít nhất là vào khoảng năm 2011.
Thuật toán này có lẽ là loại thuật toán "không tầm thường" mà bạn đã nghĩ đến. Nhưng mặt khác, việc triển khai hiệu quả LLL tương tự cũng không tầm thường (tôi đã nghe nói vài năm trước rằng LLL đồng thời là thời gian đa thức và có lẽ khó thực sự chạy trên các mạng lớn, chẳng hạn như thứ nguyên 1k +).
Điều đáng nói là dường như có một số công việc tính toán HNF bằng cách sử dụng LLL làm chương trình con, xem ví dụ cái này.
