Abstract

We exhibit a polynomial time algorithm for the NP complete problem SBQR, sizebounded quadratic residues. This establishes the equality of the complexity classes P and NP. Proof of NP completeness was given in [3]. SBQR is the set of triples of the binary representations of the positive integers a; b; c such that there exists a positive integer x satisfying x2 _ a (mod b) and x _ c. W.L.O.G. we impose a, c < b. Polynomial time means determinisic Turing machine time logO(1) b.