Primality testing (Q5904395): Difference between revisions

The author gives a summary of some known results on quadratic residues, and proves that \(n\) is prime if and only if \(\left(\frac{a}{n}\right) a^{(n-1)/2} =1\) for all \(a\) prime to \(n\). He shows that, assuming the generalized Riemann hypothesis, the number of operations needed to establish the primality of \(n\) by this criterion is \(O(log^3n \log \log \log n)\).