Computation of Irregular Primes up to Eight Million (Preliminary Report)

TitleComputation of Irregular Primes up to Eight Million (Preliminary Report)
Publication TypeTechnical Report
Year of Publication1996
AuthorsM. Shokrollahi, A.
Other Numbers1012

We report on a joint project with Joe Buhler, Richard Crandall, Reiji Ernvall, and Tauno Metnky dealing with the computation of irregular primes and cyclotomic invariants for primes between four and eight million. This extends previous computations of Buhler et al. [4]. Our computation of the irregular primes is based on a new approach which has originated in the study of Stickelberger codes [13]. It reduces the problem to that of finding zeros of a polynomial over Fp degree < (p-1)/2 among the quadratic residues. Use of fast polynomial gcd-algorithms gives an O(p log2p log log p)-algorithm for this task. By employing the Schönhage-Strassen algorithm for fast integer multiplication combined with a version of fast multiple evaluation of polynomials we design an algorithm with running time O(p log^2 p log log p). This algorithm is particularly efficient when run on primes p for which p-1 has small prime factors. We also give some improvements on the previous implementations for computing the cyclotomic invariants of a prime.

Bibliographic Notes

ICSI Technical Report TR-96-002

Abbreviated Authors

M. A. Shokrollahi

ICSI Publication Type

Technical Report