Parallel molecular computation of modular-multiplication with two same inputs over finite field GF(2~n) using self-assembly of DNA tiles

摘要

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.