title: Parallel molecular computation of modular-multiplication with two same inputs over finite field GF(2(n)) using self-assembly of DNA tiles.
abstract: Two major advantages of DNA computing - huge memory capacity and high parallelism - are being explored for large-scale parallel computing, mass data storage and cryptography. Tile assembly model is a highly distributed parallel model of DNA computing. Finite field GF(2(n)) is one of the most commonly used mathematic sets for constructing public-key cryptosystem. It is still an open question that how to implement the basic operations over finite field GF(2(n)) using DNA tiles. This paper proposes how the parallel tile assembly process could be used for computing the modular-square, modular-multiplication with two same inputs, over finite field GF(2(n)). This system could obtain the final result within less steps than another molecular computing system designed in our previous study, because square and reduction are executed simultaneously and the previous system computes reduction after calculating square. Rigorous theoretical proofs are described and specific computing instance is given after defining the basic tiles and the assembly rules. Time complexity of this system is 3n-1 and space complexity is 2n(2).
authors.affiliation: State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China; School of Computer Science and Engineering, Beihang University, Beijing 100191, China. Electronic address: liyongnan.buaa@gmail.com.
authors.forename: Yongnan
authors.initials: Y
authors.lastname: Li
authors.affiliation: State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China; School of Computer Science and Engineering, Beihang University, Beijing 100191, China. Electronic address: xiaolm@buaa.edu.cn.
authors.forename: Limin
authors.initials: L
authors.lastname: Xiao
authors.affiliation: State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China; School of Computer Science and Engineering, Beihang University, Beijing 100191, China. Electronic address: ruanli@buaa.edu.cn.
authors.forename: Li
authors.initials: L
authors.lastname: Ruan
mesh_terms: D000465:Algorithms; D039301:Computers, Molecular; D004247:DNA
chemical_list: D004247:DNA
keywords: Finite field GF(2(n)); Modular-multiplication; Modular-square; Tile assembly model