2021/04/23 by Carlos A. Cadavid, Cadavid, Carlos A., Paulina Hoyos +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Data Storage Technologies #Cellular Automata and Applications #Cryptography and Security (cs.CR) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Number Theory (math.NT) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2104.11616
openalex publication_date 2021/04/23 · openalex created_date 2023/01/25 · openalex updated_date 2026/07/28
In this article we develop an algorithm which computes a divisor of an\ninteger N, which is assumed to be neither prime nor the power of a prime. The\nalgorithm uses discrete time heat diffusion on a finite graph. If N has m\ndistinct prime factors, then the probability that our algorithm runs\nsuccessfully is at least p(m) = 1-(m+1)/2m. We compute the computational\ncomplexity of the algorithm in terms of classical, or digital, steps and in\nterms of diffusion steps, which is a concept that we define here. As we will\ndiscuss below, we assert that a diffusion step can and should be considered as\nbeing comparable to a quantum step for an algorithm which runs on a quantum\ncomputer. With this, we prove that our factorization algorithm uses at most\nO((\log N)2) deterministic steps and at most O((\log N)2) diffusion\nsteps with an implied constant which is effective. By comparison, Shor's\nalgorithm is known to use at most O((\log N)2\log (\log N) \log (\log \log\nN)) quantum steps on a quantum computer.\n As an example of our algorithm, we simulate the diffusion computer algorithm\non a desktop computer and obtain factorizations of N=33 and N=1363.\n