论文摘要
Gr?bner基（Gr?bner Bases）理论是计算机代数的一个基石,因为不仅可以知道Gr?bner基存在性,而且更为关键的是提出了计算Gr?bner基的可行性算法,所以无论是在理论上还是在计算上Gr?bner基都起着巨大的作用,近年来Gr?bner基理论的应用已经愈来愈广泛。实际上,对于与多项式相关的或者是能够将问题转化为与多项式相关的问题,Gr?bner基的理论和技巧就能发挥重要做用,于是Gr?bner基做为一种强有力的辅助工具而被广泛应用于密码学及其相关领域。然而基本的计算Gr?bner基的生成算法的计算效率是很低的,因此在一定程度上影响了Gr?bner基的实用价值。由此我们提出在现有生成算法的基础之上以并行化的方式提高其中间计算效率。本文从介绍Gr?bner基入手,首先简要介绍了求解Gr?bner基的基本理论、基本生成算法及其作用域;进而从现有的求解Gr?bner基的主流生成算法出发,先对求解算法进行分析,再介绍算法的并行相关问题及影响算法效率的关键――中间项的约化,这也是我们所主要关注的地方,我们在此过程中采用C+MPI来进行并行处理。文中首先采用结构化高斯消元法对可能产生大型稀疏矩阵予以简化,而后采用并行高斯全选主元消去法对中间项进行约化,以达到提高算法实现效率的目的;最后将Gr?bner基方法应用于零知识证明方式的身份认证,提出以采用并行的基于Gr?bner基的零知识证明与部分盲签名相结合的方式进行安全电子支付的模型,并对其交易过程和安全性进行了分析。