Related papers: An integer factorization algorithm which uses diffusion as a computational engine

An integer factorization algorithm which uses diffusion as a computational engine

URL: http://arxiv.org/abs/2104.11616v2
Date: Mon, 23 Jan 2023 18:07:56 GMT
Title: An integer factorization algorithm which uses diffusion as a computational engine
Authors: Carlos A. Cadavid, Paulina Hoyos, Jay Jorgenson, Lejla Smajlovi\'c, Juan D. V\'elez
Abstract summary: We develop an algorithm which computes a divisor of an integer $N$, which is assumed to be neither prime nor the power of a prime. By comparison, Shor's algorithm is known to use at most $O(log N)2log (log N) log (log log N)$ quantum steps on a quantum computer.
Score: 0.0
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: In this article we develop an algorithm which computes a divisor of an integer $N$, which is assumed to be neither prime nor the power of a prime. The algorithm uses discrete time heat diffusion on a finite graph. If $N$ has $m$ distinct prime factors, then the probability that our algorithm runs successfully is at least $p(m) = 1-(m+1)/2^{m}$. We compute the computational complexity of the algorithm in terms of classical, or digital, steps and in terms of diffusion steps, which is a concept that we define here. As we will discuss below, we assert that a diffusion step can and should be considered as being comparable to a quantum step for an algorithm which runs on a quantum computer. With this, we prove that our factorization algorithm uses at most $O((\log N)^{2})$ deterministic steps and at most $O((\log N)^{2})$ diffusion steps with an implied constant which is effective. By comparison, Shor's algorithm is known to use at most $O((\log N)^{2}\log (\log N) \log (\log \log N))$ quantum steps on a quantum computer. As an example of our algorithm, we simulate the diffusion computer algorithm on a desktop computer and obtain factorizations of $N=33$ and $N=1363$.