Lattice Reduction Algorithms

• LLL
• Resources

Các thuật toán rút gọn lưới nhằm mục đích lấy một cơ sở đưa ra của một lưới và biến đổi nó thành một cơ sở khác cho cùng lưới nhưng với các vector ngắn hơn và trực giao hơn. Bằng cách này, một vector lưới ngắn có thể được khôi phục. Các thuật toán thường không được thiết kế để tìm chính xác, mà là để trích xuất một vector ngắn trong một số yếu tố gần đúng, nói cách khác là để giải một số bài toán lưới khó gần đúng.

LLL

Trước tiên ta nhắc lại thuật toán Gram-Schmidt như sau:

Hai vector $\displaystyle \mathbf{u} ,\mathbf{v}$ được gọi là trực giao nếu như tích trong của chúng bằng 0 tức là $\displaystyle \langle \mathbf{u} ,\mathbf{v} \rangle =0$. Một hệ các vector $\displaystyle \mathbf{S} =(\mathbf{v_1} ,…,\mathbf{v_n})$ được gọi là một hệ trực giao nếu như chúng đôi một trực giao. Tương tự, một hệ trực giao các vector đơn vị được gọi là một hệ trực chuẩn.

Ta có thể chứng minh rằng mọi hệ trực chuẩn đều độc lập tuyến tính.

Định lí: Cho $\displaystyle \mathbf{S} =(\mathbf{v_1} ,…,\mathbf{v_n})$ là một hệ các vector độc lập tuyến tính của không gian Euclid $\displaystyle V$. Khi đó ta có thể tìm được một hệ trực chuẩn $\displaystyle \mathbf{S} ‘=(\mathbf{u_1} ,…,\mathbf{u_n})$ sao cho

$ span\{\mathbf{v_1} ,..,\mathbf{v_k}\} =span\{\mathbf{u_1} ,...,\mathbf{u_k}\} ,\forall k=1,...,n $

Để xây dựng một hệ trực chuẩn thì trước hết ta sẽ xây dựng một hệ trực giao rồi lấy từng vector chia cho chuẩn của chính nó.

Trong sage, có method gram_schmidt() cho matrix. Nó sẽ trả về một tuple bao gồm hai phần, phần đầu tiên là ma trận sau khi trực giao hóa, phần thứ hai là ma trận hệ số $\displaystyle \mu_{i,j}$ được sử dụng trong quá trình trực giao hóa.

Mình có thử viết lại thuật toán Gram-Schmidt như thế này:

from sage.all import * 

def toList(mat): 
    return [vector(QQ, mat.row(i)) for i in range(mat.nrows())]
def gram_schmidt(mat): 
    u = []
    v = toList(mat) 
    n = mat.nrows() 
    mu = Matrix(QQ, n, n, 0) 
    for i in range(n): 
        vi = v[i] 
        for j in range(i): 
            mu[i,j] = (vi * u[j]) / (u[j] * u[j]) if u[j] * u[j] != 0 else 0 
            vi = vi - mu[i,j] * u[j]
        u.append(vi) 
    for i in range(min(n,mat.ncols())):
        mu[i,i] = 1 
    return Matrix(QQ, u), Matrix(QQ, mu) 
            
def compare_mat(mat1 , mat2): 
    dif = []
    if mat1.nrows() != mat2.nrows() or mat1.ncols() != mat2.ncols(): 
        return False 
    for i in range(mat1.nrows()): 
        for j in range(mat1.ncols()): 
            if mat1[i,j] != mat2[i,j]: 
                dif.append("({}, {})".format(i,j))
    if dif:
        print("Differences at: ", dif)
        return False
    return True


def test(): 
    p = 0 
    for _ in range(100): 
        M = random_matrix(QQ, 10, 10)
        U, mu = gram_schmidt(M)
        U_, mu_ = M.gram_schmidt()
        for i in range(U.nrows()):
            for j in range(i): 
                assert U.row(i).dot_product(U.row(j)) == 0 
        res = compare_mat(U, U_) and compare_mat(mu, mu_) 
        if res: 
            p += 1 
        print(compare_mat(U, U_))
        print(compare_mat(mu, mu_))
        
    if p == 100: 
        print("All tests passed!")
    else:
        print(f"{p} out of 100 tests passed.")
        
    
if __name__ == "__main__":
    test()

Resources

• https://eprint.iacr.org/2025/774.pdf