Primality testing (Q5904395): Difference between revisions
From MaRDI portal
Latest revision as of 05:13, 13 June 2024
scientific article; zbMATH DE number 3679910
Language | Label | Description | Also known as |
---|---|---|---|
English | Primality testing |
scientific article; zbMATH DE number 3679910 |
Statements
Primality testing (English)
0 references
1980
0 references
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)\).
0 references
complexity
0 references
generalized Riemann hypothesis
0 references
primality
0 references
quadratic residues
0 references