Editing Quadratic residue (section)

===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.