一种加群Zp+上离散对数问题的DNA计算算法

摘要：

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用.研究一种加群Zp+上离散对数问题的DNA计算算法.算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成.其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间.本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数).最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性.

关键词：DNA计算、NP完全问题、密码分析、加群Zp+、离散对数问题

所属期刊栏目：39

分类号：TP306.1(计算技术、计算机技术)

资助基金：国家自然科学基金60603053,90715029;教育部新世纪优秀人才支持计划NCET-08-0177;浙江省自然科学基金Y1090264;浙江省大学生新苗计划项目851910123;嘉兴市科技计划项目2011AY1003;浙江省公益性技术应用研究计划项目2011C23130;嘉兴学院科研校内重点课题70110X01BL

在线出版日期：2012-07-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：232-235,268