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 Fp of degree<(p-1)/2 among the quadratic nonresidues mod p. Use of fast polynomial gcd- algorithms gives an O(p log~2p log log p)-algorithm for this task.