Computationally equivalent to determining if a number is a quadratic residue modulo a prime, among the algorithms proposed to solve it are an elliptic curve method named for Lenstra. Pollard's rho algorithm for achieving this iterates a polynomial formula until it falls into a cycle, while Fermat's method uses trials to find an appropriate difference of two squares and generalizes to the continued fraction method. A fast method for it is the quadratic sieve, and it can be done in polynomial time by the quantum-computational Shor's algorithm. For ten points, identify this problem in NP and co-NP, whose difficulty insures the success of RSA encryption, and which consists of breaking an integer
Computationally equivalent to determining if a number is a quadratic residue modulo a prime, among the algorithms proposed to solve it are an elliptic curve method named for Lenstra. Pollard's rho algorithm for achieving this iterates a polynomial formula until it falls into a cycle, while Fermat's method uses trials to find an appropriate difference of two squares and generalizes to the continued fraction method. A fast method for it is the quadratic sieve, and it can be done in polynomial time by the quantum-computational Shor's algorithm. For ten points, identify this problem in NP and co-NP, whose difficulty insures the success of RSA encryption, and which consists of breaking an integer into a product of primes.
Computationally equivalent to determining if a number is a quadratic residue modulo a prime, among the algorithms proposed to solve it are an elliptic curve method named for Lenstra.
integer or prime factorization