Am studiat recent algoritmul multivariat Coppersmith.
Lăsa $f(x)$ fi $n$-variază polinom peste $\mathbb{Z}_p$ pentru unele prime $p$.
În mod informal, teorema multivariată a lui Coppersmith a afirmat că, dacă ipoteza ($*$) este valabil, atunci se poate rezolva algoritmul multivariat Coppersmith în timp polinomial într-un parametru.
($*$): Există $n$ polinoame algebrice independente obținute din algoritmul LLL pe matrice $M$, unde fiecare rând de $M$ este un vector coeficient al unui multiplu al $f$ sau $p$.
Aici, pentru ușurința prezentărilor, am presupus că criteriul Calămarului este întotdeauna valabil.
Întrebările mele sunt: dacă $n$ este mare (de exemplu, n = 50 sau 100), atunci putem găsi $n$ polinoame algebric independente din $M$?
Cred că este întotdeauna imposibil de atunci $n$ este prea mare, dar nu am găsit nicio lucrare care să se ocupe de un asemenea mare $n$.
** Știu că complexitatea găsirii de polinoame multivariate presupune un cost uriaș, dar în acest subiect mă concentrez doar pe existența $n$ polinoame algebric independente.
Există vreun exemplu pentru utilizarea algoritmului multivariat Coppersmith pentru $n>5$? Am găsit doar aplicațiile algoritmului multivariat Coppersmith pe polinoame în $n = 2$ sau $3$.
Astfel, sunt oarecum confuz că algoritmul lui Coppersmith poate funcționa dacă $n>5$.
Într-adevăr, nu știu cum să obțin $n$ polinoame algebric independente dintr-un singur polinom $f$.
Mai mult, cum se garantează ipoteza ($*$) pentru unii $n = 10,20,30$? Cred că este greu să implementezi astfel de cazuri în computerele personale. În acest caz, cum să convingi că algoritmul reușește?
