近期，我院鲁东副教授最新研究成果发表在符号计算领域权威期刊《Journal of Symbolic Computation》上。鲁东副教授为该论文第一作者，合作者包括中国科学院系统所的王定康研究员、湖南师范大学的肖方慧老师和汕头大学的郑晓鹏老师。《Journal of Symbolic Computation》是由欧洲科学院院士Bruno Buchberger教授于1985年创办的符号计算领域的权威期刊，我国著名数学家吴文俊院士曾担任该期刊的第一届编委。该杂志涉及的研究领域包括计算代数、计算几何（非线性）、符号计算语言和系统的设计与实现等。目前该期刊是中国数学会推荐的T2期刊。
图1 论文发表首页
科学与工程领域中的大量理论和实际问题均可化归为多项式系统求解问题，比如几何定理机器证明、破解著名的AES-128加密体制等。目前，多项式系统的求解方法分为数值方法、符号方法以及符号—数值混合方法，不同的方法适用于不同的实际问题，比如密码攻击问题只适合用符号方法进行求解。基于符号方法在密码分析、几何建模等领域发挥的重要作用，本文重点关注如何设计高效的多项式系统符号求解方法。
2002年，法国计算机科学家J.-C. Faugère教授从如何减少冗余计算的角度出发，基于签名技术提出了著名的F5算法，并成功攻破了HFE密码系统。然而，F5算法的理论复杂且算法终止性存在问题。2011年，中国科学院信息工程研究所王明生研究员与美国克莱姆森大学S. Gao教授等人提出了基于签名技术的GVW算法。相较于F5算法，GVW算法的理论更加简洁明了，且保证了算法的终止性。在交换代数中，有时需要考虑不同环中多项式系统的求解问题，比如代数簇的奇点消解问题。因此，符号计算领域中的众多学者开始研究如何设计局部环上的签名标准基算法，但始终无法解决算法终止性问题。
基于GVW算法的框架，鲁东老师与合作者利用推广的Mora范式算法克服无限集合没有极小元的困难，给出任意半群序下的签名标准基算法，首次从理论上证明算法的正确性和终止性。该签名标准基算法是多项式环上GVW算法的进一步推广，它适用于所有的项序，包括全局序、局部序和混合序，使得在任何情形下均可使用该算法进行多项式系统的高效求解。匿名评审人评价“this work is a leap forward in signature Gröbner bases”。
图 2 任意半群序下的签名标准基算法
该研究受到国家重点研发计划（No.: 2020YFA0712300）、国家自然科学基金（Nos.: 12171469, 12201210, 12001030）、四川省自然科学基金（No.: 2024NSFSC0418）以及中央高校基本科研业务费（No.: 2682024ZTPY052）等项目的资助。
原文链接:
https://www.sciencedirect.com/science/article/pii/S0747717124000749
