Phân tích ra thừa số trong trường hữu hạn

Bài toán phân tích một số nguyên ra thừa số nguyên tố là một bài toán khó, thuật toán tốt nhất để giải nó có độ phức tạp dưới mũ. Hiện chưa có thuật toán trong thời gian đa thức nào để giải nó. Và nếu có một thuật toán như vậy, hệ mật mã RSA đang dùng khắp nơi sẽ sụp đổ.

Điều đó làm ta có đôi chút bất ngờ khi xem xét bài toán phân tích trong trường hữu hạn. Bởi ta có thể hình dung, trong trường hữu hạn, các đa thức bất khả quy có thể xem như các số nguyên tố và việc phân tích một đa thức thành các tích các đa thức bất khả quy cũng na ná như phân tích một số nguyên thành thừa số nguyên tố. Vậy nhưng, bài toán phân tích trong trường hữu hạn lại có thể giải được trong thời gian đa thức. Bài này ta tìm hiểu tại sao phân tích trong trường hữu hạn lại dễ thế.

I. Khởi động: các đa thức bất khả quy

Vai trò của đa thức bất khả quy là phần tử cơ bản đối với việc xây dựng một trường hữu hạn mở rộng. Với mỗi số nguyên tố \(p\), ta có trường cơ bản \(F_p\). Để mở rộng được một trường \(F_q\) có \(q = p^n\) phần tử, ta cần có một đa thức bất khả quy bậc \(n\) với hệ số trong \(F_p\), rồi để mở rộng tiếp từ \(F_q\) lên \(F_{q^r}\) ta cần một đa thức bất khả quy bậc \(r\) với hệ số trong \(F_q\).

Vậy ta lấy những đa thức bất khả quy từ đâu ra? Cũng như câu hỏi: kiếm đâu ra các số nguyên tố? Và cũng như việc sinh các số nguyên tố, cách thường làm là ta sinh ra một số bất kỳ rồi kiểm tra xem nó có là số nguyên tố hay không, đối với trường hữu hạn, ta sẽ sinh một đa thức bất kỳ rồi kiểm tra xem nó có là bất khả quy hay không. Sự khác biệt đầu tiên ta có thể thấy: việc kiểm tra tính nguyên tố của một số nguyên là tương đối khó, đến tận năm 2002 mới có thuật toán tất định thực hiện điều đó, nhưng việc kiểm tra một đa thức trong một trường hữu hạn có bất khả quy hay không thì lại tương đối dễ.

Ta biết rằng trên một trường hữu hạn \(F\) có \(q\) phần tử, tập tất cả các nghiệm của đa thức \(X^q - X\) chính là tập các phần tử của \(F\) (dễ thấy vì hiển nhiên mọi phần tử của \(F\) đều là nghiệm của nó, và đa thức bậc \(q\) nên không thể có quá \(q\) nghiệm). Diễn đạt một cách khác thì \(X^q - X\) chính là tích của tất cả các đa thức bậc một (do vậy, bất khả quy) \((X - a)\) với \(a \in F\). Tổng quát hóa lên, không khó khăn lắm để thấy được \(X^{q^2} - X\) là tích của tất cả các đa thức bất khả quy bậc hai trở xuống, và tổng quát hơn, \(X^{q^d} - X\) là tích của tất cả các đa thức bất khả quy bậc \(r\) với \(r \mid d\).

Đến đây thì việc kiểm tra xem một đa thức \(f\) bậc \(r\) có bất khả quy hay không dễ như trở bàn tay: trước hết kiểm tra \(X^{q^r} \equiv X \pmod f\); sau đó, với mọi \(1 \leq i \leq \lfloor r/2 \rfloor\), dùng thuật toán Euclid tính \(\gcd(f, X^{q^i} - X)\). Nếu tất cả các ước chung lớn nhất này đều là \(1\) thì ta có kết luận \(f\) là bất khả quy. Sở dĩ ta có thuật toán hiệu quả kiểm tra một đa thức bất khả quy hay không (so với kiểm tra một số tự nhiên nguyên tố hay không) là bởi ta gộp được các đa thức bất khả quy.

Cũng từ việc \(X^{q^d} - X\) là tích của tất cả các đa thức bất khả quy bậc \(r\) với \(r \mid d\), ta có thể dễ dàng ước lượng phân bố các đa thức bất khả quy. Ký hiệu \(\Pi(r)\) là số các đa thức bất khả quy monic bậc \(r\), thì số lượng các hệ số của tích trên cho ta đẳng thức

Từ đó dễ thấy bằng quy nạp rằng \(\dfrac{q^d}{2} < d \cdot \Pi(d) < q^d\). Nói cách khác, trong tổng số \(q^d\) đa thức monic bậc \(d\) thì có \(O\!\left(\dfrac{q^d}{d}\right)\) đa thức bất khả quy. Đặt \(N = q^d\) thì ta có ước lượng số các đa thức bất khả quy là \(O\!\left(\dfrac{N}{\log_q N}\right)\), và điều thú vị là đó cũng chính là ước lượng số các số nguyên tố nhỏ hơn \(N\) (định lý số nguyên tố: \(\pi(N) \sim N / \ln N\)).

II. Thuật toán Berlekamp cho bài toán phân tích

Ý tưởng chính của cả bài toán phân tích số \(N\) lẫn phân tích đa thức \(f\) đều xuất phát từ một điểm cơ bản: tìm một căn bậc hai ngẫu nhiên của phần tử đơn vị!

Với số tự nhiên \(N\), giả sử \(N = p_1^{e_1} \times \cdots \times p_k^{e_k}\). Khi đó ta đã biết có đẳng cấu vành

Phần tử \(1\) tương ứng với bộ \((1, \ldots, 1)\), và các căn bậc hai của \(1\) tương ứng với các bộ \((\pm 1, \ldots, \pm 1)\) (chọn độc lập dấu \(\pm\) ở mỗi vị trí).

Nếu ta có một căn bậc hai \(V\) ngẫu nhiên của \(1\), với xác suất đáng kể thì sẽ có bộ có cả dấu cộng lẫn dấu trừ. Do vậy \(V - 1\) sẽ có ít nhất một tọa độ là \(0\) và ít nhất một tọa độ khác \(0\). Chỉ cần tính \(\gcd(V - 1,\, N)\) là ta tìm được một nhân tử không tầm thường của \(N\).

Vấn đề khó ở đây là tìm được một căn bậc hai ngẫu nhiên của phần tử đơn vị trong \(\mathbb{Z}/N\mathbb{Z}\). Vấn đề này khá hóc búa đối với số tự nhiên, và đến nay chỉ có thuật toán dưới mũ để giải nó.

Rất may là trong trường hữu hạn, ta có thể thực hiện điều đó khá dễ dàng trong thời gian đa thức.

Cho đa thức \(f\) với hệ số trên trường \(F\) có \(q\) phần tử. Để đơn giản, trước hết ta giả sử \(f\) không có nhân tử lặp, tức là \(f\) square-free; trong thuật toán đầy đủ, ta có thể dùng \(\gcd(f,f')\) để tách phần có nhân tử lặp trước. Tương tự như với số nguyên, nếu \(f = f_1 \times \cdots \times f_r\) (các \(f_i\) bất khả quy, phân biệt), thì \(E = F[X]/f\) là một vành mở rộng và ta có đẳng cấu

Từ một căn bậc hai ngẫu nhiên của phần tử đơn vị trong \(E\), ta có thể tìm được một nhân tử của \(f\) hoàn toàn tương tự như cách làm với số tự nhiên. (Ở đây ta bỏ qua một số trường hợp đặc biệt cần xét riêng như trường đặc số \(2\) hay khi \(f\) có nhân tử kép \(f_i^2\).)

Bây giờ là nguyên nhân cơ bản để ta có thể tìm một căn bậc hai ngẫu nhiên của phần tử đơn vị trong \(E\).

Xét tập

Tập \(B\) có vai trò vô cùng quan trọng, vì nếu ta bắt được một phần tử ngẫu nhiên \(u \in B\) thì coi như xong: khi đó \(u^{(q-1)/2}\) là một căn bậc hai ngẫu nhiên của phần tử đơn vị trong \(E\).

Ta hãy xem cấu trúc của \(B\). Khi \(f\) là bất khả quy, tập \(B\) bao gồm các phần tử bất biến qua phép ánh xạ Frobenius, và \(B\) đích thị là trường \(F\) — không có gì thêm để nói. Tuy nhiên khi \(f = f_1 \times \cdots \times f_r\) như trên, tập \(B\) sẽ là không gian vectơ \(r\) chiều trên \(F\). Thực vậy, mỗi thành phần \(F[X]/f_i\) là một mở rộng trường, và tập các \(x \in F[X]/f_i\) thỏa mãn \(x^q = x\) chính là \(F\) (bất biến qua Frobenius). Do vậy, theo đẳng cấu \((*)\), tập \(B\) tương ứng với tập tất cả các bộ \((c_1, \ldots, c_r)\) với \(c_i \in F\) — tức \(B\) là không gian vectơ \(r\) chiều trên \(F\).

Ta biết cấu trúc của \(B\) như vậy, nhưng làm sao để tóm được một phần tử ngẫu nhiên của nó? Vì \(B\) là không gian vectơ, chỉ cần tóm được một hệ cơ sở của \(B\) thì ta sẽ sinh ra được các phần tử của \(B\). Vậy vấn đề chuyển thành tìm một hệ cơ sở của \(B\). Nhưng khi không biết \(f_1, \ldots, f_r\) thì ta cũng không biết \(B\), nên tóm được hệ cơ sở nghe chừng không dễ.

Nhưng thực ra thì lại rất dễ! Quay trở lại vành \(E\) mà ta sở hữu, và xét ánh xạ

Ánh xạ \(\mu\) là một ánh xạ tuyến tính trên \(F\), và tập \(B\) chính là hạt nhân (kernel) của \(\mu\):

Đến đây, việc xây dựng cơ sở cho \(B\) là dễ dàng thực hiện được qua đại số tuyến tính cơ bản, vì ta hoàn toàn kiểm soát được ánh xạ \(\mu\): ta xây dựng ma trận \(M\) ứng với ánh xạ \(\mu\) (kích thước \(\deg f \times \deg f\), với hệ số trong \(F\)), sau đó dùng phép khử Gauss-Jordan trên \(M\) để tìm hệ cơ sở cho \(\ker(M)\), tức chính là cho \(B\).

Có được hệ cơ sở của \(B\), ta sinh ra một phần tử ngẫu nhiên \(u \in B\), tính \(u^{(q-1)/2}\) — một căn bậc hai ngẫu nhiên của đơn vị — và từ đó dùng \(\gcd\) để tách nhân tử của \(f\). Đây chính là nội dung cốt lõi của thuật toán Berlekamp.