Buhler, J.Crandall, R.Ernvall, R.Mesänkylä, T.Shokrollahi, A2007-01-162007-01-162007-01-16200110.1006/jsco.1999.1011https://infoscience.epfl.ch/handle/20.500.14299/239474Computations of irregular primes and associated cyclotomic invariants were extended to all primes up to twelve 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 Fp of degree &st (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 Schönhage- 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 primealgoweb_numbertheoryalgoweb_compalgtext::journal::journal article::research article