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.