I recently studied the multivariate Coppersmith algorithm.
Let $f(x)$ be $n$-variate polynomial over $\mathbb{Z}_p$ for some prime $p$.
Informally, the multivariate Coppersmith's theorem stated that if the assumption ($*$) holds, then one can solve the multivariate Coppersmith's algorithm in polynomial time in some parameter.
($*$): There exist $n$ algebraic independent polynomials obtained from the LLL algorithm on the matrix $M$, where each row of $M$ is a coefficient vector of a multiple of $f$ or $p$.
Here, for the ease presentations, I assumed that the Coppersmith's criterion always holds.
My questions are: if $n$ is large, (e.g., n = 50 or 100), then, can we find $n$ algebraically independent polynomials from $M$?
I think it is always impossible since $n$ is too large, but I could not find any paper that deals with such a large $n$.
** I know that the complexity of finding multivariate polynomials takes a huge cost, but in this thread, I only focus on the existence of $n$ algebraically independent polynomials.
Is there any example for using the multivariate Coppersmith's algorithm for $n>5$? I only found the applications of the multivariate Coppersmith's algorithm on polynomials in $n = 2$ or $3$.
Thus, I'm somewhat confused that the Coppersmith's algorithm can actually work if $n>5$.
Indeed, I do not know how to obtain $n$ algebraically independent polynomials from a single polynomial $f$.
Moreover, how to guarantee the assumption ($*$) for some $n = 10,20,30$? I think that it is hard to implement such cases in personal computers. In this case, how to convince that the algorithm succeed?
