Primality testing (Q5904395): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4149785 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Evaluation and comparison of two efficient probabilistic primality testing algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topics in multiplicative number theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4164569 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Fast Monte-Carlo Test for Primality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4175613 / rank | |||
Normal rank |
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