Fast parallel DNA-based algorithms for molecular computation: quadratic congruence and factoring integers.

Department of Computer Science and Information Engineering,National Kaohsiung University of Applied Sciences, Kaohsiung City,Taiwan. changwl@cc.kuas.edu.tw

IEEE transactions on nanobioscience 2012 Mar

filter terms:

Assume that n is a positive integer. If there is an integer such that M (2) ≡ C (mod n), i.e., the congruence has a solution, then C is said to be a quadratic congruence (mod n). If the congruence does not have a solution, then C is said to be a quadratic noncongruence (mod n). The task of solving the problem is central to many important applications, the most obvious being cryptography. In this article, we describe a DNA-based algorithm for solving quadratic congruence and factoring integers. In additional to this novel contribution, we also show the utility of our encoding scheme, and of the algorithm's submodules. We demonstrate how a variety of arithmetic, shifted and comparative operations, namely bitwise and full addition, subtraction, left shifter and comparison perhaps are performed using strands of DNA.

Citation

Weng-Long Chang. Fast parallel DNA-based algorithms for molecular computation: quadratic congruence and factoring integers. IEEE transactions on nanobioscience. 2012 Mar;11(1):62-9