Quadratic residue
In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
Otherwise, q is called a quadratic nonresidue modulo n.
Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers.
The for all odd prime divisors p of n.
Legendre symbol
Applications of quadratic residues
Acoustics
Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.[39]
Graph theory
Paley graphs are dense undirected graphs, one for each prime p ≡ 1 (mod 4), that form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices.
Paley digraphs are directed analogs of Paley graphs, one for each p ≡ 3 (mod 4), that yield antisymmetric conference matrices.
The construction of these graphs uses quadratic residues.
Cryptography
The fact that finding a square root of a number modulo a large composite n is equivalent to factoring (which is widely believed to be a hard problem) has been used for constructing cryptographic schemes such as the Rabin cryptosystem and the oblivious transfer. The quadratic residuosity problem is the basis for the Goldwasser-Micali cryptosystem.
The discrete logarithm is a similar problem that is also used in cryptography.
Primality testing
Euler's criterion is a formula for the Legendre symbol (a|p) where p is prime. If p is composite the formula may or may not compute (a|p) correctly. The Solovay–Strassen primality test for whether a given number n is prime or composite picks a random a and computes (a|n) using a modification of Euclid's algorithm,[40] and also using Euler's criterion.[41] If the results disagree, n is composite; if they agree, n may be composite or prime. For a composite n at least 1/2 the values of a in the range 2, 3, ..., n − 1 will return "n is composite"; for prime n none will. If, after using many different values of a, n has not been proved composite it is called a "probable prime".
The Miller–Rabin primality test is based on the same principles. There is a deterministic version of it, but the proof that it works depends on the generalized Riemann hypothesis; the output from this test is "n is definitely composite" or "either n is prime or the GRH is false". If the second output ever occurs for a composite n, then the GRH would be false, which would have implications through many branches of mathematics.
Integer factorization
In § VI of the Disquisitiones Arithmeticae[42] Gauss discusses two factoring algorithms that use quadratic residues and the law of quadratic reciprocity.
Several modern factorization algorithms (including Dixon's algorithm, the continued fraction method, the quadratic sieve, and the number field sieve) generate small quadratic residues (modulo the number being factorized) in an attempt to find a congruence of squares which will yield a factorization. The number field sieve is the fastest general-purpose factorization algorithm known.
The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.