Fast Quantum Algorithms of Solving an Instance of Quadratic Congruence on a Quantum Computer
Weng-Long Chang, Mang Feng · 2012
It is assumed that P is the product of two prime numbers q1and q2. If there is an integer 02= C (mod P), i.e., the congruence has a solution, then C is said to be a quadratic congruence (mod P). Quadratic congruence (mod P) is a NP-complete problem. If the value of C is equal to one, then four integer solutions for M2= 1 (mod P) are, respectively, b, P - b, 1 and P - 1, where 12= 1 (mod P) can be found by means of the proposed quantum algorithms with polynomial quantum gates, polynomial quantum bits and the successful probability that is the same as that of Shor's order-finding algorithm.