I. Giới thiệu về dàn và cơ sở rút gọn
Chương này trình bày các khái niệm cơ bản về dàn và thuật toán rút gọn cơ sở (thuật toán LLL). Dàn là một nhóm con của nhóm cộng Rn, đẳng cấu với Zn và sinh ra không gian véctơ Rn. Thuật toán rút gọn cơ sở được đề xuất bởi Lenstra, Lenstra và Lovász (LLL) nhằm tìm một cơ sở rút gọn của dàn với thời gian đa thức. Thuật toán này có nhiều ứng dụng trong toán học ứng dụng và lý thuyết mã hóa. Phần này cũng phân tích tính dừng của thuật toán LLL, chứng minh rằng thuật toán luôn kết thúc sau hữu hạn bước.
1.1 Khái niệm về dàn
Dàn trong không gian Rn được định nghĩa là một nhóm con của nhóm cộng Rn, đẳng cấu với Zn. Một cơ sở của dàn là tập các véctơ độc lập tuyến tính sinh ra dàn đó. Chuẩn của dàn được tính bằng định thức của ma trận các véctơ cơ sở, đại diện cho thể tích hình hộp được sinh bởi các véctơ này. Ví dụ, trong R2, dàn được sinh bởi hai véctơ f1 = (12, 2) và f2 = (13, 4) có chuẩn là 22, tương ứng với diện tích hình bình hành dựng trên hai véctơ này.
1.2 Thuật toán rút gọn cơ sở của Lenstra Lenstra và Lovász
Thuật toán LLL là một phương pháp hiệu quả để tìm một cơ sở rút gọn của dàn. Thuật toán này dựa trên quá trình trực giao hóa Gram-Schmidt và các phép biến đổi tuyến tính để giảm độ dài của các véctơ cơ sở. Một cơ sở được gọi là rút gọn nếu thỏa mãn điều kiện kfi∗k2 ≤ 2kfi+1∗k2 với mọi 1 ≤ i < n. Thuật toán LLL đảm bảo tìm được một cơ sở rút gọn sau hữu hạn bước, với độ phức tạp thời gian đa thức.
1.3 Tính dừng của thuật toán rút gọn cơ sở
Tính dừng của thuật toán LLL được chứng minh thông qua việc xác định một số nguyên D liên quan đến thể tích của các hình hộp cơ sở. Số này giảm mỗi khi xảy ra bước trao đổi hai véctơ cơ sở, đảm bảo thuật toán kết thúc sau hữu hạn bước. Các bổ đề chuẩn bị trong phần này cung cấp cơ sở toán học để chứng minh tính dừng của thuật toán, bao gồm các bước làm mới và trao đổi véctơ cơ sở.
II. Một số ứng dụng của thuật toán rút gọn cơ sở
Chương này trình bày các ứng dụng thực tiễn của thuật toán rút gọn cơ sở trong nhiều lĩnh vực khác nhau. Thuật toán LLL không chỉ có ý nghĩa lý thuyết mà còn được áp dụng rộng rãi trong phân tích đa thức, giải phương trình toàn phương, phá vỡ hệ mã hóa, và xấp xỉ Diophant. Các ứng dụng này minh họa tính linh hoạt và hiệu quả của thuật toán trong việc giải quyết các bài toán phức tạp.
2.1 Phân tích đa thức thành nhân tử
Thuật toán LLL được sử dụng để phân tích đa thức với hệ số hữu tỉ thành nhân tử. Phương pháp này dựa trên việc tìm các véctơ ngắn trong dàn liên quan đến các hệ số của đa thức. Kết quả là một thuật toán hiệu quả để phân tích đa thức, đặc biệt hữu ích trong lý thuyết số và đại số.
2.2 Giải phương trình toàn phương
Thuật toán LLL cũng được áp dụng để giải các phương trình toàn phương. Bằng cách rút gọn cơ sở của dàn liên quan đến phương trình, thuật toán giúp tìm các nghiệm nguyên hoặc hữu tỉ một cách hiệu quả. Ứng dụng này có ý nghĩa quan trọng trong lý thuyết số và toán học ứng dụng.
2.3 Phá vỡ các hệ mã kiểu ba lô
Một trong những ứng dụng nổi bật của thuật toán LLL là trong mật mã học, cụ thể là phá vỡ các hệ mã kiểu ba lô. Thuật toán giúp tìm các véctơ ngắn trong dàn liên quan đến hệ mã, từ đó giải mã thông tin một cách hiệu quả. Ứng dụng này minh họa tầm quan trọng của thuật toán trong an ninh thông tin.
