Irregular primes and cyclotomic invariants to 12 million

Computations of irregular primes and associated cyclotomic invariants were extended to all primes up to 12 million using multisectioning/convolution m ethods and a novel approach which originated in the study of Stickelberger codes (Shokrollahi, 1996). The latter idea reduces the problem to that of f inding zeros of a polynomial over F-p of degree < (p - 1)/2 among the quadr atic nonresidues mod p. Use of fast polynomial gcd-algorithms gives an O(p log(2) p log log p)-algorithm for this task. A more efficient algorithm, wi th comparable asymptotic running time, can be obtained by using Schonhage-S trassen integer multiplication techniques and fast multiple polynomial eval uation algorithms; this approach is particularly efficient when run on prim es p for which p - 1 has small prime factors. We also give some improvement s on previous implementations for verifying the Kummer-Vandiver conjecture and for computing the cyclotomic invariants of a prime. (C) 2001 Academic P ress.