Arithmetic Computation Using Self-Assembly of DNA Tiles: Modular-Square over Finite Field GF(2n)

Author

Yongnan Li ; Limin Xiao ; Li Ruan ; Aihua Liang

Author_Institution

State Key Lab. of Software Dev. Environ., Beihang Univ., Beijing, China

fYear

2013

fDate

13-15 Nov. 2013

Firstpage

490

Lastpage

495

Abstract

Tile assembly model is a highly distributed parallel model of DNA computing. This paper proposes how the tile assembly process could be used for computing the modular square, an operation combining square and reduction, over finite field GF(2ⁿ). In this molecular computing system, reduction is executed after the completion of square. The time complexity of this molecular computing system is ⊙(n) and the space complexity is ⊙(n²). This system requires 75 types of computation tiles and 9 types of boundary tiles.

Keywords

Galois fields; biocomputing; computational complexity; digital arithmetic; self-assembly; DNA computing; arithmetic computation; assembly model; distributed parallel model; finite field GF(2ⁿ); modular square computation; molecular computing system; space complexity; tile self-assembly process; time complexity; Assembly; Assembly systems; Biological system modeling; Computational modeling; DNA; DNA computing; Tiles; DNA computing; Finite field GF(2n); Modular-square; Tile assembly model;

fLanguage

English

Publisher

ieee

Conference_Titel

High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing (HPCC_EUC), 2013 IEEE 10th International Conference on

Conference_Location

Zhangjiajie

Type

conf

DOI

10.1109/HPCC.and.EUC.2013.76

Filename

6831958