因子分解问题的DNA计算机算法

摘 要

近年来,我国的分子生物学得到了较大程度的发展.再此过程中,高性能计算机的出现也为我们分子生物学的研究提供了更好的研究基础,其所具有的高运算能力、海量存储等特点都能够对以往我们不能实现的问题提供了解决可能.在本文中,将就因子分解问题的DNA计算机算法进行一定的分析与研究.

【关 键 词】因子分解问题DNA计算机算法研究

1引言

计算机的出现,成功的帮助人们从以往各项工作的繁重计算任务中得到了解脱,无论是对于学术上的研究还是社会的发展都具有着非常大的作用.但是,计算机往往对于计算方式简单的计算问题具有较好的胜任能力,但是对于数学层面上的NP完全问题以及难解问题在实际解决过程中却具有着较大的难度,所获得的计算效果也不是很好.对此,就需要我们通过新技术的研究来解决此项问题,其中,DNA计算机就是一种有效的方式.

2DNA计算机算法原理

2.1DNA计算原理

在该种算法中,我们通过DNA结构所存在的特殊双螺旋及碱基互补配对原则对于相关的计算问题进行编码处理,将需要我们开展计算的对象通过一系列方式的应用将其转化为DNA分子链,以此在生物酶的影响将相关DNA溶液分解成不同的数据池,并通过相关的规则将这部分原始问题以高度并行、实际运算的方式映射为分子链可控化的一个过程,进而在完成该项工作后通过分子生物技术的应用获得计算结果.

2.2DNA计算优势

所谓DNA计算机,属于一种特殊形式下的新型计算机,其通过DNA有机分子作为开关元件,同我们日常所使用的计算机相比具有着更大的优势：

2.2.1高度并行性

DNA计算机在实际运算过程中具有着更快的计算速度,在Adleman试验中,通过专家的科学估计,认为其DNA串并行操作的数目已经能够达到1014,甚至部分专家认为在现有的技术条件下,DNA计算机的方式甚至可以实现1020以内的串并行操作数目.同时,对于目前的计算机来说,其中所具有的每一个操作都是非常缓慢的,但是DNA计算机所具有的并行性优势却能够较好的帮助我们对这个缺陷进行弥补.而对于规模极大的操作来说,DNA计算机能够在同一时间对同一问题的不同部分进行计算,在对数据价目标准DES问题进行解决时具有着非常好的运行效果.

2.2.2高强密集度

对于DNA来说,属于一种信息载体,具有着非常大的储存容量.在1m3的DNA溶液中,能够帮助我们存储1万亿亿二进制数据,而这种密集度甚至会远远超过了目前全国电子计算机的总储存量.另外,DNA计算机还具有着非常高的可靠性,属于半永久性计算机.

3具体算法

在具体计算方面,主要是以Pollard-1DNA方式对因子分解工作进行实现,对于我们即将分解的整数n来以及需要首先制定的界B来说,可以事先通过平方乘的方式对2Bmodn进行计算,并将其暂计为a,之后再通过欧吉里德算法将a-1同n之间所存在的最大公因子进行计算,以此帮助我们实现对n进行分解的目的.而在这个过程中,我们主要所开展的计算都是通过常规分子生物的操作对该项计算任务进行实现,其主要的算法如下所示：

3.1通过数字计算机将B、n、a转换成二进制

第一,我们需要对n的二进制进行转换,,在m1,m2,---,md中,m1是最低位,md是最高位,其长度我们可以设为l-n,

第二,对于a这个参数来说,其所具有的初始值为2,而a的二进制转换则为c2,1,c2,2,---,c2,k.其中,c2,1为最低位,c2,k则为最高位,

第三,对于该种算法而言,其主要对应的就是我们对平方乘算法进行计算中乘法运算所具有的两种不同情况,并在这个过程中对乘法器进行初始化.其中一种的所求结果就是乘以a,而另一种则是需要对所得结果的平方进行获取.

3.2通过欧吉里德DNA算法计算因子d

在此计算过程中,需要我们先求a-1的解,之后再通过欧几里德算法的应用对式中的a-1以及n的最大公因子进行计算,之后再进行其除法运算,并以此种方式得到余数序列nk+2,1---nk+2,k.在这个序列中,nk+2,1为最低位,而nk+2,k则为最高位,当对该序列进行实际判断时,如果其中的余数值为.0,则可以获得所得到的结果,并终止该算法.

3.ollardp-1因子分解DNA算法

通过Pollardp-1分解算法的应用,能够帮助我们获取DNA中大数n的因子.首先,我们需要获得初始化试管T的值,判断其值是否为0.如果经过判断得到其值为0,则需要对计算结果进行提取,并停止运行程序.而如果经过计算该值非0,则需要对试管T中的余数进行计算,并当试管中具有DNA链时将其中的试管值读给T,在对其初始化之后执行相关程序,以此帮助我们获得大数n中的一个因子.

4结束语

在上文中,我们对因子分解问题的DNA计算机算法进行了一定的研究.而为了能够获得更好的计算效果,就需要我们在计算的同时也需要不断的对算法进行改进、优化,以此来最大程度的提升计算精度.