| 一种加群Z上离散对数问题的DNA计算算法 |
| |
| 引用本文： | 周 旭,李肯立,乐光学,朱开乐.一种加群Z上离散对数问题的DNA计算算法[J].计算机科学,2012,39(4):232-235,268. |
| |
| 作者姓名： | 周 旭 李肯立 乐光学 朱开乐 |
| |
| 作者单位： | (嘉兴学院数理与信息工程学院 嘉兴314001);(湖南大学信息科学与工程学院 长沙410082) |
| |
| 基金项目： | 国家自然科学基金(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计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。
|
| 关 键 词： | DNA计算 NP完全问题 密码分析 加群Zp+离散对数问题 |
Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Z DNA-based Computing |
| |
| ZHOU Xu,LI Ken-li,YUE Guang-xue,ZHU Kai-le.Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Z DNA-based Computing[J].Computer Science,2012,39(4):232-235,268. |
| |
| Authors: | ZHOU Xu LI Ken-li YUE Guang-xue ZHU Kai-le |
| |
| Affiliation: | 1(College of Mathematics and Information Engineering,Jiaxing University,Jiaxing 314001,China)1(School of Computer and Communications,Hunan University,Changsha 410082,China)2 |
| |
| Abstract: | The discrete logarithm problem over group 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(kz)biological operations, O(1) test tubes, O(2k) DNA sequences, and the maximum length of the DNA sequence is O(kz).Finally, the common test methods were used to verify the new algorithm's feasibility and effectiveness. |
| |
| Keywords: | DNA-based computing NP-complete problem Cryptoanalysis Discrete logarithm problem ever group Zp |
| 本文献已被 CNKI 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
