title: Fast parallel molecular algorithms for DNA-based computation: factoring integers.
abstract: The RSA public-key cryptosystem is an algorithm that converts input data to an unrecognizable encryption and converts the unrecognizable data back into its original decryption form. The security of the RSA public-key cryptosystem is based on the difficulty of factoring the product of two large prime numbers. This paper demonstrates to factor the product of two large prime numbers, and is a breakthrough in basic biological operations using a molecular computer. In order to achieve this, we propose three DNA-based algorithms for parallel subtractor, parallel comparator, and parallel modular arithmetic that formally verify our designed molecular solutions for factoring the product of two large prime numbers. Furthermore, this work indicates that the cryptosystems using public-key are perhaps insecure and also presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.
authors.affiliation: Department of Information Management, Southern Taiwan University of Technology, Tainan, Taiwan. changwl@mail.stut.edu.tw
authors.forename: Weng-Long
authors.initials: WL
authors.lastname: Chang
authors.forename: Minyi
authors.initials: M
authors.lastname: Guo
authors.forename: Michael Shan-Hui
authors.initials: MS
authors.lastname: Ho
mesh_terms: D000465:Algorithms; D016494:Computer Security; D039301:Computers, Molecular; D003205:Computing Methodologies; D004247:DNA / Q000737:chemistry* / Q000235:genetics; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D017422:Sequence Analysis, DNA / Q000379:methods*; D012815:Signal Processing, Computer-Assisted
chemical_list: D004247:DNA