Cyclotomy primality proving -- recent developments

DOI10.1007/BFB0054854MaRDI QIDQ3840153zbMATH OpenFDO

Authors Preda Mihaĭlescu

Publication date 18 March 1999

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

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

zbMATH Keywords

cyclotomy primalitydeterministic algorithmelliptic curvesGalois theoretic primality tests

Mathematics Subject Classification ID

Factorization; primality (11A51) Cyclotomic extensions (11R18) Primality (11Y11)

Review text

Der Artikel stellt eine Kurzfassung der Dissertation des Autors dar, die sich mit neuen Überlegungen und Implementierungen des ``Galois-Theorie-Primzahl-Tests gefaßt. Dieser war von \textit{H. W. Lenstra jun.} angeregt worden [Semin. Bourbaki Exp. No. 576, Lect. Notes Math. 901, 243-257 (1981; Zbl 0476.10005)] als Kombination des Gauß-Jacobi-Summen-Tests von \textit{L. Adleman}, \textit{C. Pomerance} und \textit{R. Rumely} [Ann. Math. (2) 117, 173-206 (1983; Zbl 0526.10004)] und des Lucas-Lehmer-Tests. Wie schon seine Vorgänger hat auch der hier diskutierte ``Kreisteilungs-Primzahl-Test eine asymptotische Laufzeit \[ {\mathcal O}(\log n^{c\log\log\log n}), \] ist aber deterministisch und im Bereich der überhaupt zugänglichen \(n\) (bis etwa \(10^{1000}\)) dem konkurrierenden ECPP-Test, der mit elliptischen Kurven arbeitet, überlegen. Allerdings läßt er sich nicht wesentlich beschleunigen, wenn nur ein Beweis der Primzahleigenschaft beabsichtigt ist. For the entire collection see [Zbl 0891.00022].

Recommendations

• Recent developments in primality proving
• Recent developments in primality testing
• Algorithms for relatively cyclotomic primes
• scientific article; zbMATH DE number 4123798
• scientific article; zbMATH DE number 3827966
• Primary cyclotomic units and a proof of Catalans conjecture
• On the Cyclotomic Main Conjecture for the prime 2
• Primality proving using elliptic curves: An update
• Some Conjectures About Cyclotomic Integers
• scientific article; zbMATH DE number 2211811

Cited in

(5)

• Complete congruences of Jacobi sums of order \(2l^2\) with prime \(l\)
• scientific article; zbMATH DE number 3910467 (Why is no real title available?)
• scientific article; zbMATH DE number 4123798 (Why is no real title available?)
• scientific article; zbMATH DE number 1954367 (Why is no real title available?)
• Computation of Jacobi sums of orders l^2 and 2l^2 with odd prime l

This page was built for publication: Cyclotomy primality proving -- recent developments

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