Primality testing

DOI10.1016/0304-3975(80)90008-0MaRDI QIDQ5904395zbMATH OpenOpenAlexFDO

Authors Maurice Mignotte

Publication date 1980

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(80)90008-0

zbMATH Keywords

complexitygeneralized Riemann hypothesisprimalityquadratic residues

Mathematics Subject Classification ID

Power residues, reciprocity (11A15) Primality (11Y11)

Review text

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)\).

Recommendations

• Primality testing
• scientific article; zbMATH DE number 3957201
• scientific article; zbMATH DE number 17386
• Primality tests
• Primality tests
• Testing numbers for primality
• scientific article; zbMATH DE number 6308078
• scientific article; zbMATH DE number 1263352

Cites work

• A Fast Monte-Carlo Test for Primality
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• scientific article; zbMATH DE number 3578903 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 3609741 (Why is no real title available?)
• Topics in multiplicative number theory

Cited in

(8)

• Miller's primality test
• Quadratic Polynomials which have a High Density of Prime Values
• scientific article; zbMATH DE number 3981247 (Why is no real title available?)
• scientific article; zbMATH DE number 1263352 (Why is no real title available?)
• On the complexity of testing primality by homogeneous structures
• scientific article; zbMATH DE number 6308078 (Why is no real title available?)
• On a combined primality test
• Primality tests

This page was built for publication: Primality testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5904395)