Editing Quadratic residue (section)

==Applications of quadratic residues==

===Acoustics===

[[Diffusion (acoustics)#Quadratic-residue diffusors|Sound diffusers]] have been based on number-theoretic concepts such as [[primitive root modulo n|primitive roots]] and quadratic residues.<ref>{{cite web|last=Walker|first=R|title=The design and application of modular acoustic diffusing elements|url=http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf|publisher=BBC Research Department|access-date=25 October 2016}}</ref>

===Graph theory===

[[Paley graph]]s are dense undirected graphs, one for each prime ''p'' ≡ 1 (mod 4), that form an infinite family of [[conference graph]]s, which yield an infinite family of [[symmetric matrix|symmetric]] [[conference matrix|conference matrices]].

Paley digraphs are directed analogs of Paley graphs, one for each ''p'' ≡ 3 (mod 4), that yield [[Skew-symmetric matrix|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 [[Computational hardness assumption|hard problem]]) has been used for constructing [[cryptography|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,<ref>{{Harvnb|Bach|Shallit|1996|p=113}}</ref> and also using Euler's criterion.<ref>{{Harvnb|Bach|Shallit|1996|pp=109&ndash;110}}; Euler's criterion requires O(log<sup>3</sup> ''n'') steps</ref> 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'' &minus; 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''<ref>Gauss, DA, arts 329&ndash;334</ref> 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 factorization|continued fraction method]], the [[quadratic sieve]], and the [[General number field sieve|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.