0
$\begingroup$

I'm studying algorithms solving multivariate equations. I'm stuck in solving overdetermined set of quadratic equations. Concretely, with the number $n$ of variables, the number of equations is $m=\epsilon n^2$. If $\epsilon\geq 1/2$, it is known that trivial linearization solves the set of equations. However, in the case that $\epsilon<1/2$, the trivial linearization seems not working anymore.

But there are some papers suggesting that if $\epsilon$ is somewhat large ($1/16<\epsilon<1/2$) then the system of equations can be solved in $O(n^{2\omega})$-time where $2\leq\omega\leq3$ is linear algebra constant. Efficient algorithms for solving overdefined systems of multivariate polynomial equations claimed that the time complexity of XL algorithm is $O(n^{\omega\lceil\frac 1 {\sqrt{\epsilon}}\rceil})$. It implies that if $1/4\leq \epsilon<1/2$ then the time complexity is $O(n^{2\omega})$. But I cannot catch the case.

One more paper here. Complexity of Groebner basis computation for semi-regular overdetermined sequences over F_2 with solutions in F_2 claimed that the degree of regularity is asymptotically $\max(1/8\epsilon,2)$ which implies that if $1/16\leq \epsilon<1/2$ then the time complexity of F5 algorithm is $O(n^{2\omega})$.

For both cases, I don't know how the algorithms can get such time complexity (when maximal degree of XL or F5 computation is 2). Are those my missings or just asymptotics not for the cases?

Comment: This question was originally asked on Stack Exchange Cryptography. I duplicate the question for the reason that some of those who are not in cryptography will be able to solve this problem better. After getting a reply, I will remove the not-answered question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.