Abstract
A Galois field G F ( p n ) <math><mrow><mspace></mspace> <mi>G</mi> <mi>F</mi> <mrow><mo>(</mo> <mrow> <msup><mrow><mi>p</mi></mrow> <mrow><mi>n</mi></mrow> </msup> </mrow> <mo>)</mo></mrow> </mrow> </math> with p ≥ 2 <math><mrow><mspace></mspace> <mi>p</mi> <mo>≥</mo> <mn>2</mn></mrow> </math> a prime number and n ≥ 1 <math><mrow><mi>n</mi> <mo>≥</mo> <mn>1</mn></mrow> </math> is a mathematical structure widely used in Cryptography and Error Correcting Codes Theory. In this paper, we propose a novel DNA-based model for arithmetic over G F ( p n ) <math><mrow><mspace></mspace> <mi>G</mi> <mi>F</mi> <mrow><mo>(</mo> <mrow> <msup><mrow><mi>p</mi></mrow> <mrow><mi>n</mi></mrow> </msup> </mrow> <mo>)</mo></mrow> </mrow> </math> . Our model has three main advantages over other previously described models. First, it has a flexible implementation in the laboratory that allows the realization arithmetic calculations in parallel for p ≥ 2 <math><mrow><mspace></mspace> <mi>p</mi> <mspace></mspace> <mo>≥</mo> <mn>2</mn></mrow> </math> , while the tile assembly and the sticker models are limited to p = 2 <math><mrow><mi>p</mi> <mo>=</mo> <mn>2</mn></mrow> </math> . Second, the proposed model is less prone to error, because it is grounded on conventional Polymerase Chain Reaction (PCR) amplification and gel electrophoresis techniques. Hence, the problems associated to models such as tile-assembly and stickers, that arise when using more complex molecular techniques, such as hybridization and denaturation, are avoided. Third, it is simple to implement and requires 50 ng/μL per DNA double fragment used to develop the calculations, since the only feature of interest is the size of the DNA double strand fragments. The efficiency of our model has execution times of order O ( 1 ) <math><mrow><mspace></mspace> <mi>O</mi> <mrow><mo>(</mo> <mrow><mn>1</mn></mrow> <mo>)</mo></mrow> </mrow> </math> and O ( n ) <math><mrow><mspace></mspace> <mi>O</mi> <mrow><mo>(</mo> <mrow><mi>n</mi></mrow> <mo>)</mo></mrow> </mrow> </math> , for the addition and multiplication over G F ( p n ) <math><mrow><mspace></mspace> <mi>G</mi> <mi>F</mi> <mrow><mo>(</mo> <mrow> <msup><mrow><mi>p</mi></mrow> <mrow><mi>n</mi></mrow> </msup> </mrow> <mo>)</mo></mrow> </mrow> </math> , respectively. Furthermore, this paper provides one of the few experimental evidences of arithmetic calculations for molecular computing and validates the technical applicability of the proposed model to perform arithmetic operations over G F ( p n ) <math><mrow><mi>G</mi> <mi>F</mi> <mrow><mo>(</mo> <mrow> <msup><mrow><mi>p</mi></mrow> <mrow><mi>n</mi></mrow> </msup> </mrow> <mo>)</mo></mrow> </mrow> </math> .