Gần đây tôi đã nghiên cứu thuật toán Coppersmith đa biến.
Để cho $f(x)$ thì là ở $n$-biến đa thức thành $\mathbb{Z}_p$ cho một số nguyên tố $p$.
Một cách không chính thức, định lý Coppersmith đa biến phát biểu rằng nếu giả định ($*$) giữ, sau đó người ta có thể giải thuật toán Coppersmith đa biến trong thời gian đa thức trong một số tham số.
($*$): Có tồn tại $n$ đa thức độc lập đại số thu được từ thuật toán LLL trên ma trận $M$, trong đó mỗi hàng của $M$ là một vectơ hệ số của một bội số của $f$ hoặc $p$.
Ở đây, để dễ trình bày, tôi giả định rằng tiêu chuẩn của Coppersmith luôn đúng.
Câu hỏi của tôi là: nếu $n$ lớn, (ví dụ: n = 50 hoặc 100), thì chúng ta có thể tìm $n$ đa thức độc lập đại số từ $M$?
Tôi nghĩ rằng nó luôn luôn là không thể kể từ khi $n$ quá lớn, nhưng tôi không thể tìm thấy bất kỳ bài báo nào đề cập đến một kích thước lớn như vậy $n$.
** Tôi biết rằng việc tìm đa thức phức tạp tốn rất nhiều chi phí, nhưng trong chủ đề này, tôi chỉ tập trung vào sự tồn tại của $n$ các đa thức độc lập đại số.
Có ví dụ nào về việc sử dụng thuật toán Coppersmith đa biến cho $n>5$? Tôi chỉ tìm thấy các ứng dụng của thuật toán Coppersmith đa biến trên đa thức trong $n = 2$ hoặc $3$.
Vì vậy, tôi hơi bối rối rằng thuật toán của Coppersmith thực sự có thể hoạt động nếu $n>5$.
Thực sự, tôi không biết làm thế nào để có được $n$ đa thức độc lập đại số từ một đa thức duy nhất $f$.
Hơn nữa, làm thế nào để đảm bảo giả định ($*$) cho một số $n = 10,20,30$? Tôi nghĩ rằng thật khó để thực hiện những trường hợp như vậy trong máy tính cá nhân. Trong trường hợp này, làm thế nào để thuyết phục rằng thuật toán thành công?
