Quadratic residuosity problem
Problem in computational number theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Quadratic residuosity problem?
Summarize this article for a 10 year old
The quadratic residuosity problem (QRP[1]) in computational number theory is to decide, given integers and , whether is a quadratic residue modulo or not. Here for two unknown primes and , and is among the numbers which are not obviously quadratic non-residues (see below).
The problem was first described by Gauss in his Disquisitiones Arithmeticae in 1801. This problem is believed to be computationally difficult. Several cryptographic methods rely on its hardness, see § Applications.
An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether a composite of unknown factorization is the product of 2 or 3 primes.[2]