按照信息论与密码学先驱Shannon的观点，密码学的大多数问题可以转化为有限域上代数方程组的求解问题。多变量多项式方程求解的困难性是很多密码体系，包括流密码、分组密码、多变元公钥密码，其安全性的数学保证。有限域上非线性多变量方程求解的量子算法研究，是密码设计与分析的关键问题。

国家数学与交叉科学中心先进制造部的科研人员在有限域上非线性方程求解与优化的量子算法方面取得重要进展。他们根据布尔环上的量子算法，设计了有限域上方程求解与优化的量子算法。这一算法在方程组对应的矩阵条件数不高的情况下，量子算法能达到指数级加速。进一步地，将有限域上方程组求解问题更一般化，扩充为包含有限域上变元以及含有界整数变元的含非线性约束的优化问题。这一问题包含了很多应用，比如含噪声的多项式系统求解(polynomial systems with noise), 小整数解问题(short integer solution problem)， Number Theory Research Unit (NTRU)， 背包问题等。 上述这些算法的提出，揭示了在量子计算模型下，基于有限域上方程组求解与优化的相应密码体制的安全度依赖于其所对应的扩展矩阵的条件数。

来源：国家数学与交叉科学中心网