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

Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Z_p^+ DNA-based Computing

作　　者：周旭[1] 李肯立[2] 乐光学[1] 朱开乐[1] 

机构地区：[1]嘉兴学院数理与信息工程学院,嘉兴314001 [2]湖南大学信息科学与工程学院,长沙410082

出　　处：《计算机科学》2012年第4期232-235,268,共5页Computer Science

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

摘　　要：加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。The discrete logarithm problem over group Z＋p is widely applied in the public key cryptosystems.We proposed a new DNA computing algorithm to solve the problem.Our new algorithm consists of an initial solution generator,a parallel multiplier,an invalid parallel detector,a parallel conventor and a parallel solution searcher.For the sake of reducing the DNA sequences required in the new algorithm,the solution space will be generated considering the three-list algorithm.The proposed algorithm needs O（k2） biological operations,O（1） test tubes,O（2k） DNA sequences,and the maximum length of the DNA sequence is O（k2）.Finally,the common test methods were used to verify the new algorithm＇s feasibility and effectiveness.

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

分 类 号：TP306.1[自动化与计算机技术—计算机系统结构]