Calculating Cyclotomic Polynomials
Andrew Arnold, Michael Monagan
Last updated:
Wed Feb 3 18:04:43 PST 2010
The algorithms:
Download our paper:
Calculating Cyclotomic Polynomials (PDF, 236 KB)
Submitted Oct 10, 2008 to the Mathematics of Computation.
We used two algorithms. The first algorithm calculates cyclotomic polynomials using the FFT to perform fast polynomial division.
This method was superceded by an algorithm which calculates cyclotomic polynomials as a quotient of products of power series.
We have implementations of this algorithm that compute cyclotomic polynomials to 64, 96, and 128-bit precision.
Many cyclotomic polynomials we want to calculate are too high a degree to be able to store in main memory at 128-bit precision. In addition, we've found a few cyclotomic polynomials with coefficients greater than 2^128.
To calculate these polynomials also have implementations that compute cyclotomic polynomials modulo many 1B, 2B, 4B, or 8B primes, allowing us to calculate cyclotomic polynomials to arbitrarily high precision.
We tried to calculate \Phi_{99660932085}(z) by computing it mod 32 bit primes (each roughly 76 GB). This required computation to be done on the harddisk. Each image took roughly two weeks to compute. We computed five images, after which the harddisk crashed. We do not recommend this approach.
In lieu of recent improvements to the sparse power series algorithm, we now feel that it is possible to compute the height of \Phi_{99660932085}(z).
Results
Data on the heights and lengths of cyclotomic polynomials:
Heights and Lenghts of Cyclotomic Polynomials
- Heights and lenghts of $\Phi_n(z)$ of order 3, for squarefree, odd n<1.00*10^8
- Heights and lenghts of $\Phi_n(z)$ of order 4, for squarefree, odd n<2.25*10^8
- Heights and lenghts of $\Phi_n(z)$ of order 5, for squarefree, odd n<5.10*10^8
- Heights and lenghts of $\Phi_n(z)$ of order 6, for squarefree, odd n<7.70*10^8
- Heights and lenghts of $\Phi_n(z)$ of order 7, for squarefree, odd n<2.01*10^9
- Heights and lenghts of $\Phi_n(z)$ of order 8, for squarefree, odd n<5.20*10^9
- Heights and lengths of $\Phi_n(z)$ of order 9
Heights and Lengths of Inverse Cyclotomic Polynomials
- Heights and lenghts of $\Psi_n(z)$ of order 3, for squarefree, odd n<1.00*10^8
- Heights and lenghts of $\Psi_n(z)$ of order 4, for squarefree, odd n<1.00*10^8
- Heights and lenghts of $\Psi_n(z)$ of order 5, for squarefree, odd n<2.40*10^8
- Heights and lenghts of $\Psi_n(z)$ of order 6, for squarefree, odd n<5.00*10^8
- Heights and lenghts of $\Psi_n(z)$ of order 7, for squarefree, odd n<1.00*10^9
- Heights and lenghts of $\Psi_n(z)$ of order 8, for squarefree, odd n<2.00*10^9
References
[1] A. S. Bang. Om ligningen Ï (x) = 0. Nyt Tidsskrift for Mathematik,
(6):6â, 1895.
[2] P. T. Bateman, C. Pomerance, and R. C. Vaughan. On the size of the
coefficients of the cyclotomic polynomial. In Topics in classical number
theory, Vol. I, II (Budapest, 1981), volume 34 of Colloq. Math. Soc. Janos
Bolyai, pages 171â2. North-Holland, Amsterdam, 1984.
[3] D. M. Bloom. On the coefficients of the cyclotomic polynomials. Amer.
Math. Monthly, 75:372â7, 1968.
[4] Wieb Bosma. Computation of cyclotomic polynomials with Magma. In
Computational algebra and number theory (Sydney, 1992), volume 325 of
Math. Appl., pages 213â5. Kluwer Acad. Publ., Dordrecht, 1995.
[5] Paul Erdos and R.C. Vaughn. On the coefficients of the cyclotomic poly-
nomial. Bull. Amer. Math. Soc., 52:179â4, 1946.
[6] Keith O. Geddes, Stephen R. Czapor, and George Labahn. Algorithms for
Computer Algebra. Kluwer Academic Publishers, Boston, 1992.
[7] A. Grytczuk and B. Tropak. A numerical method for the determination
of the cyclotomic polynomial coefficients. In Computational number theory
(Debrecen, 1989), pages 15â. de Gruyter, Berlin, 1991.
[8] Yoichi Koshiba. On the calculations of the coefficients of the cyclotomic
polynomials. Rep. Fac. Sci. Kagoshima Univ., (31):31â, 1998.
[9] Yoichi Koshiba. On the calculations of the coefficients of the cyclotomic
polynomials. II. Rep. Fac. Sci. Kagoshima Univ., (33):55â, 2000.
[10] Helmut Maier. The size of the coefficients of cyclotomic polynomials. In
Analytic number theory, Vol. 2 (Allerton Park, IL, 1995), volume 139 of
Progr. Math., pages 633â9. Birkhauser Boston, Boston, MA, 1996.
[11] R. Thangadurai. On the coefficients of cyclotomic polynomials. In
Cyclotomic fields and related topics (Pune, 1999), pages 311â2.
Bhaskaracharya Pratishthana, Pune, 2000.
[12] Joachim von zur Gathen and Jurgen Gerhard. Modern computer algebra.
Cambridge University Press, Cambridge, second edition, 2003.