计算机科学 ›› 2012, Vol. 39 ›› Issue (4): 232-235.

• 人工智能 • 上一篇    下一篇

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

周 旭,李肯立,乐光学,朱开乐   

  1. (嘉兴学院数理与信息工程学院 嘉兴314001);(湖南大学信息科学与工程学院 长沙410082)
  • 出版日期:2018-11-16 发布日期:2018-11-16

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

  • Online:2018-11-16 Published:2018-11-16

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

关键词: DNA计算,NP完全问题,密码分析,加群侧离散对数问题

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.

Key words: DNA-based computing, NP-complete problem, Cryptoanalysis, Discrete logarithm problem ever group Zp.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!