Factoring Gaussian Integers: A Quantum Algorithm
Mingwei Wu · 2021 2nd International Conference on Electronics, Communications and Information Technology (CECIT) · 2021
In this paper, we developed a quantum algorithm for factoring Gaussian integers based on Shor's Algorithm. It is one of the problems that are intractable for classical computers but are manageable for quantum computers. An efficient quantum algorithm for factoring is influential in the application of cryptography because a large portion of the current cryptographic schemes rely on the assumption that factoring is difficult. We also discuss potential generalizations of our algorithm to other algebraic integers.