Primality testing in polynomial time. From randomized algorithms to ``PRIMES is in P.

DOI10.1007/b12334zbMath1058.11070OpenAlexW2476552886MaRDI QIDQ1882154

Martin Dietzfelbinger

Publication date: 19 October 2004

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b12334

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Primality (11Y11)

Related Items

Mechanisation of AKS Algorithm: Part 1 – The Main Theorem, Prime simplicity, Encoding binary arithmetic operations in integer programming formulations, Mechanisation of the AKS algorithm, A certain family of subgroups of \(\mathbb{Z}_{n}^{\star}\) is weakly pseudo-free under the general integer factoring intractability assumption