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 methods and a novel approach which originated in the study of Stickelberger codes (Shokrollahi, 1996). The latter idea reduces the problem to that of finding zeros of a polynomial over F-p of degree (p - 1)/2 among the quadratic 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, with comparable asymptotic running time, can be obtained by using Schonhage-Strassen integer multiplication techniques and fast multiple polynomial evaluation algorithms; this approach is particularly efficient when run on primes p for which p - 1 has small prime factors. We also give some improvements on previous implementations for verifying the Kummer-Vandiver conjecture and for computing the cyclotomic invariants of a prime. (C) 2001 Academic Press.