*(English)*Zbl 0768.11009

The authors have calculated the irregular pairs $(p,k)$ for all primes $p<{10}^{6}$. Recall that a pair $(p,k)$ is called irregular if $k$ is an even integer with $2\le k\le p-3$ such that $p$ divides the numerator of the Bernoulli number ${B}_{k}$. Previous computations of the irregular pairs, covering the range $p<150\phantom{\rule{4pt}{0ex}}000$ [see *J. W. Tanner* and *S. S. Wagstaff*, ibid. 48, 341–350 (1987; Zbl 0613.10012)], used algorithms requiring $O\left({p}^{2}\right)$ arithmetic operations for each prime $p$. The present authors were able to reduce this number to $O(plogp)$. They computed Bernoulli numbers modulo $p$ basically from the formula

performing the power series inversion by algorithms based on the fast Fourier transform and multisectioning of power series. The maximum number of irregular pairs $(p,k)$ found in this range was 6, occurring for $p=527377$.

The authors also used their results to verify that Fermat’s “Last Theorem” and Vandiver’s conjecture are true for the primes $p<{10}^{6}$.

{A subsequent work by the first two authors together with *R. Ernvall* and the reviewer [ibid., July 1993 issue] extends the above calculations to all primes below four million and moreover gives the ordinary cyclotomic invariants for these primes}.

##### MSC:

11B68 | Bernoulli and Euler numbers and polynomials |

11D41 | Higher degree diophantine equations |

65Y20 | Complexity and performance of numerical algorithms |

11R18 | Cyclotomic extensions |

11Y55 | Calculation of integer sequences |

68Q25 | Analysis of algorithms and problem complexity |