基于DNA计算自组装模型的Diffie-Hellman算法破译(英文)

被引：4

作者：

陈智华

机构：

[1] 华中科技大学控制科学与工程系

来源：

计算机学报 | 2008年 / 31卷 / 12期

关键词：

DNA计算; DNA自组装模型; 离散对数; 整数排序; PCR;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

DNA自组装计算模型是近年来引人关注的计算模型,已有基于自组装模型的二进制加法、乘法以及有限域中的加法和乘法的讨论.文中利用DNA自组装模型设计的模乘系统,实现了素数p的本原根g连续乘方后模p的数的排列,从而可以在线性时间内求解离散对数,为破译Diffie-Hellman密钥交换算法提供了新的生物方法.该模乘系统使用了Θ(p)种自组装类型,组装的时间复杂度为Θ(p-1).系统最后组装结果提取出报告链后,经过PCR和凝胶电泳读取离散对数结果.该模型扩展了DNA自组装计算模型的应用,为求取离散对数提供了新思路.

引用

页码：2116 / 2122

页数：7

共 5 条

[1]

Solid phase based DNA solution of the coloring problem[J]. PAN Linqiang , LIU Guangwu, XU Jin and LIU Yachun (1. Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China;2. Research Group on Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tarraco 1, 43005 Tarragona, Spain;3. Department of Mathematical and Physical Science, Nanhua University, Hengyang 421001, China).Progress in Natural Science. 2004(05)

[2]

Arithmetic computation in the tile assembly model: Addition and multiplication[J] . Yuriy Brun.Theoretical Computer Science . 2006 (1)

[3]

Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes[J] . Linqiang Pan,Carlos Martín-Vide.Journal of Parallel and Distributed Computing . 2005 (12)

[4] Algorithmic self-assembly of DNA Sierpinski triangles [J].

Rothemund, PWK ;

Papadakis, N ;

Winfree, E .

PLOS BIOLOGY, 2004, 2 (12) :2041-2053

[5] Cryptography with DNA binary strands [J].

Leier, A ;

Richter, C ;

Banzhaf, W ;

Rauhe, H .

BIOSYSTEMS, 2000, 57 (01) :13-22

← 1 →