Arithmetic computation in the tile assembly model: Inversion over finite field GF(2n)

Tile assembly model is a formal model of DNA computing, which uses DNA, biochemistry and molecular biology instead of the traditional silicon-based computer technologies. DNA-based cryptography is an interdisciplinary area combining classical cryptography and molecular computing. This paper proposes how the tile assembly process could be used for computing inversion over finite field GF(2ⁿ), a basic mathematic operation often used in cryptography. This computing system is designed based on two other parallel molecular computing systems proposed in our previous works. Time complexity of this system is Θ(n²) and the space complexity is Θ(n⁴).