A polynomial-time algorithm for solving a class of underdetermined multivariate quadratic equations
A polynomial-time algorithm for solving a class of underdetermined multivariate quadratic equations
复制标题
求解一类欠定多元二次方程的多项式时间算法
DOI：
10.1007/978-3-319-11659-4_3
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
and T. Takagi
中科院分区：
文献类型：
--
作者：
C.-M. Cheng;Y. Hashimoto;H. Miura;and T. Takagi
继Kipnis-Patarin-Goubin、Courtois-Goubin-Meier-Tacier和Kipnis-Wolf的一系列工作之后，Miura、Hashimoto和Takagi在PQCrypto 2013中提出了求解一类欠定多元二次方程的有效算法。他们的算法不使用任何通用的Gröbner基求解技术和渐近需要在所有类似的算法在当前文献中的欠定程度最低。建立在他们的工作之上，在本文中，我们专注于解决多项式欠定多元二次方程的领域奇的特点。我们表明，我们可以进一步提高的Miura-Hashimoto-Takagi算法的适用范围基本上是免费的。此外，我们展示了如何允许一定程度的适用范围和运行时间之间的权衡。最后，我们证明了改进算法的运行时间实际上是多项式的方程和变量的数量。据我们所知，这是第一个结果表明，这类多项式欠定的多元二次方程的奇数特征域可以在多项式时间内解决。
Following up a series of works by Kipnis-Patarin-Goubin, Courtois-Goubin-Meier-Tacier, and Thomae-Wolf, in PQCrypto 2013 Miura, Hashimoto, and Takagi proposed an efficient algorithm for solving a class of underdetermined multivariate quadratic equations. Their algorithm does not use any generic Gröbner-basis solving techniques and asymptotically requires the least degree of underdeterminedness among all similar algorithms in the current literature. Building on top of their work, in this paper we focus on solving polynomially underdetermined multivariate quadratic equations over fields of odd characteristics. We show that we can further improve the applicable range of the Miura-Hashimoto-Takagi algorithm essentially for free. Furthermore, we show how to allow a certain degree of trade-off between applicable range and running time. Last but not least, we show that the running time of the improved algorithm is actually polynomial in number of equations and variables. To the best of our knowledge, this is the first result showing that this class of polynomially underdetermined multivariate quadratic equations over fields of odd characteristics can be solved in polynomial time.