潘森杉胡予濮 王保仓
(西安电子科技大学综合业务网国家重点实验室 西安 710071)
基于标签的矩阵型Gröbner基算法研究
潘森杉*胡予濮 王保仓
(西安电子科技大学综合业务网国家重点实验室 西安 710071)
目前基于标签的Gröbner基算法大多是Buchberger型的,涉及矩阵型算法的文献往往是为了进行复杂度分析,而不考虑实际的效率。该文从实际应用出发,给出矩阵型Gao-Volny-Wang(GVW)算法的一个实例,提出算法层次的优化设计方法。同时,该文还给出一个高效的约化准则。通过实验,该文比较了算法可用的各项准则及策略。实验结果表明,该文的矩阵型GVW实例在准则和策略的选取上是最优的。并且,矩阵型GVW在某些多项式系统(例如,Cyclic系列和Katsura系列多项式系统)下比Buchberger型GVW要快2~6倍。
密码学;Gröbner基;标签;多项式;Gao-Volny-Wang (GVW)算法
Gröbner基是求解多元多项式系统的一个基本数学工具。求出了多项式组的Gröbner基,多项式系统的解就能很快算出。这一工具广泛应用于编码理论、密码学乃至物理、生物等自然科学领域。1965年,Buchberger[1]提出了第1个Gröbner基求解算法。1983年,为了分析Buchberger算法的复杂度,Lazard引入了线性代数的方法[2]。随后Faugère提出了基于线性代数的F4算法[3]和基于标签的F5算法[4]。F4, F5算法是目前公认的两个高效Gröbner基求解算法。Faugère和Joux在文献[5]中使用了矩阵F5算法成功地攻破了隐藏域方程(Hidden Field Equations, HFE)公钥密码系统的第1个挑战(80 bit)。虽然源码未曾公开,文献[6, 7]给出其算法的伪代码,文献[8]给出一个更详细的矩阵算法版本。矩阵F5算法的核心思想是借鉴F4中线性代数的方法来同时约化多个多项式。……