Editing Solovay–Strassen primality test (section)

==Concepts==
[[Leonhard Euler|Euler]] proved<ref>[[Euler's criterion]]</ref> that for any odd [[prime number]] ''p'' and any integer ''a'',

:<math>a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p </math>

where <math>\left(\tfrac{a}{p}\right)</math> is the [[Legendre symbol]]. The [[Jacobi symbol]] is a generalisation of the Legendre symbol to <math>\left(\tfrac{a}{n}\right)</math>, where ''n'' can be any odd integer. The Jacobi symbol can be computed in time [[big O notation|O]]((log&nbsp;''n'')²) using Jacobi's generalization of the
[[quadratic reciprocity|law of quadratic reciprocity]].

Given an odd number ''n'' one can contemplate whether or not the congruence

:<math> a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n</math>

holds for various values of the "base" ''a'', given that ''a'' is [[Coprime integers|relatively prime]] to ''n''.  If ''n'' is prime then this congruence is true for all ''a''.  So if we pick values of ''a'' at random and test the congruence, then 
as soon as we find an ''a'' which doesn't fit the congruence we know that ''n'' is not prime (but this does not tell us a nontrivial factorization of ''n''). This base ''a'' is called an ''Euler witness'' for ''n''; it is a witness for the compositeness of ''n''. The base ''a'' is called an ''Euler liar'' for ''n'' if the congruence is true while ''n'' is composite.

For every composite odd ''n'', at least half of all bases

:<math>a \in (\mathbb{Z}/n\mathbb{Z})^* </math>

are (Euler) witnesses as the set of Euler liars is a proper subgroup of <math>(\mathbb{Z}/n\mathbb{Z})^*</math>. For example, for <math> n =65</math>, the set of Euler liars has order 8 and <math> = \{1,8,14,18,47,51,57,64\}</math>, and <math>(\mathbb{Z}/n\mathbb{Z})^*</math> has order 48.

This contrasts with the [[Fermat primality test]], for which the proportion of witnesses may be much smaller.  Therefore, there are no (odd) composite ''n'' without many witnesses, unlike the case of [[Carmichael number]]s for Fermat's test.