Fast Parallel DNA-Based Algorithms for Molecular Computation: Quadratic Congruence and Factoring Integers

Assume that is a positive integer. If there is an integer such that , i.e., the congruence has a solution, then is said to be a quadratic congruence . If the congruence does not have a solution, then is said to be a quadratic noncongruence . 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.