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

Area of Science:

• Computational Biology
• Number Theory
• Cryptography

Background:

• Quadratic congruences are fundamental in number theory and have critical applications in cryptography.
• Solving these congruences and integer factorization are computationally challenging problems.

Purpose of the Study:

• To present a novel DNA-based algorithm for solving quadratic congruences.
• To demonstrate the application of this algorithm for integer factorization.
• To showcase the utility of a specific DNA encoding scheme and its submodules.

Main Methods:

• Development of a DNA-based algorithm tailored for number theoretic problems.
• Implementation of DNA strand operations to perform arithmetic and comparative functions.
• Encoding of integers and congruence relations into DNA sequences.

Main Results:

• Successful demonstration of a DNA algorithm for solving quadratic congruences.
• Validation of the algorithm's capability for integer factorization.
• Proof of concept for DNA-based computation of essential arithmetic operations like addition, subtraction, and comparison.

Conclusions:

• The proposed DNA-based algorithm offers a novel approach to solving quadratic congruences and factoring integers.
• The study highlights the potential of DNA computing for complex mathematical and cryptographic tasks.
• The developed DNA encoding scheme and submodules are effective for computational number theory.