学位论文 > 优秀研究生学位论文题录展示

Gr(?)bner基生成算法的并行

作　者: 狄鹏
导　师: 马文平
学　校: 西安电子科技大学
专　业: 通信与信息系统
关键词: Gr(o ¨)bner基 MPI 高斯消元法零知识证明
分类号: TP301.6
类　型: 硕士论文
年　份: 2008年
下　载: 17次
引　用: 1次
阅　读: 论文下载

内容摘要

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基的零知识证明与部分盲签名相结合的方式进行安全电子支付的模型,并对其交易过程和安全性进行了分析。

全文目录

摘要  3-4
Abstract  4-5
参考符号  5-7
第一章绪论  7-11
第二章 Gr(o|¨) bner基理论  11-25
  2.1 算术代数知识  11-12
  2.2 项序  12-14
  2.3 除法算法  14-15
  2.4 域上的Gr(o|¨) bner基  15-19
  2.5 环上的Gr(o|¨) bner基  19-23
  2.6 主理想环上的Gr(o|¨) bner基  23-25
第三章 Gr(o|¨) bner基的生成算法及其并行  25-43
  3.1 并行计算简介  25-27
  3.2 生成算法伪代码  27-34
  3.3 算法并行及分析  34-40
  3.4 实验实例结果检验  40-43
第四章 Gr(o|¨) bner基的并行化应用  43-53
  4.1 信息安全  43-44
  4.2 零知识证明  44-45
  4.3 基于Gr(o|¨) bner基的零知识证明  45-46
  4.4 盲签名与部分盲签名  46-47
  4.5 实例  47-51
  4.6 小结  51-53
第五章结束语  53-55
  5.1 小结  53-54
  5.2 发展趋势  54-55
致谢  55-57
参考文献  57-63
附录  63-65
作者读研期间发表的论文和参与的科研项目  65-66

Gr(?)bner基生成算法的并行

内容摘要

全文目录

相似论文