Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

Author: Greg Stein
Journal: Math. Comp. 70 (2001), 1237-1251
MSC (2000): Primary 11T06, 11T24, 11T22; Secondary 12Y05, 13P05
Published electronically: March 24, 2000
MathSciNet review: 1709159
Full-text PDF

Abstract | References | Similar Articles | Additional Information


We examine the problem of factoring the $r$th cyclotomic polynomial, $\Phi _r(x),$ over $\mathbb{F}_p$, $r$ and $p$ distinct primes. Given the traces of the roots of $\Phi _r(x)$ we construct the coefficients of $\Phi _r(x)$ in time $O(r^4)$. We demonstrate a deterministic algorithm for factoring $\Phi _r(x)$ in time $O((r^{1/2+\epsilon}\log p)^9)$ when $\Phi _r(x)$ has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of $\Phi _r(x)$ in time $O(r^6)$.

References [Enhancements On Off] (What's this?)

  • 1. L.D. Baumert and W.H. Mills, Uniform cyclotomy, J. Number Theory, [14], (1982), pp. 67-82. MR 83f:10005
  • 2. B.C. Berndt, R.J. Evans and K.S. Williams, ``Gauss and Jacobi Sums'', Wiley, New York, 1998. MR 99d:11092
  • 3. D. Bini and V. Pan, ``Polynomial and Matrix Computations'', Birkhauser, Boston, 1994. MR 95k:65003
  • 4. D. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp., [36], (1981), pp. 587-592. MR 82e:12020
  • 5. H. Cohen, ``A Course in Computational Algebraic Number Theory'', Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1995. MR 94i:11105
  • 6. L.E. Dickson, Cyclotomy, higher congruences, and Waring's problem, Amer. J. Math., [57], (1935), pp. 391-424.
  • 7. S.A. Evdokimov, Factorization of a solvable polynomial over finite fields and the generalized Riemann Hypothesis, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) [176], (1989), pp. 104-117, 153. MR 91a:11063
  • 8. C. F. Gauss,``Disquisitiones Arithmeticae'', Springer-Verlag, New York, 1986. MR 87f:01105
  • 9. M.A. Huang, Generalized Riemann Hypothesis and factoring polynomials over finite fields, J. Algorithms, [12], (1991), pp. 464-481. MR 92j:68057
  • 10. D. Jungnickel, Finite fields. Structure and arithmetics. Bibliographisches Institut, Mannheim, 1993. MR 94g:11109
  • 11. D. Knuth,``The Art of Computer Programming'', volume 2, Semi-numerical algorithms, 3rd ed., Addison-Wesley, Reading, 1998. MR 83i:68003
  • 12. S. Lang, ``Algebra'', Addison-Wesley, Reading, 1965. MR 33:5416
  • 13. R. Lidl and H. Niederreiter, ``Introduction to Finite Fields and their Applications'', revised edition, Cambridge University Press, Cambridge, 1994. MR 95f:11098
  • 14. R. Lidl and H. Niederreiter, ``Finite Fields'', Encyclopedia of Mathematics and its Applications, v.20, Addison-Wesley, Reading, 1983. MR 86c:11106
  • 15. G. B. Mathews, ``Theory of Numbers'', Chelsea, New York, 1961. MR 23:A3698
  • 16. G. Myerson, Period polynomials and Gauss sums for finite fields, Acta Arith., [39], (1981), pp. 251-264. MR 83e:10058
  • 17. H. Niederreiter and R. Göttfert, On a new factorization algorithm for polynomials over finite fields, Math. Comp., [ 64], (1995), pp. 347-353. MR 95i:11145
  • 18. R. Schoof, Elliptic curves over finite fields and the computation of square roots $\operatorname{mod}$ $p,$ Math. Comp. [44 ], (1985), pp. 483-494. MR 86e:11122
  • 19. V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. [54], (1990), pp. 435-447. MR 90j:11135
  • 20. G. Stein, Factoring cyclotomic polynomials over large finite fields, in ``Finite Fields and Applications'', London Mathematical Society Lecture Note Series #233, S. Cohen & H. Niederreiter, eds., Cambridge University Press, pp. 349-354, 1996. MR 98b:11122
  • 21. G. Stein, Traces of roots of unity over prime fields, in ``Finite Fields: Theory, Applications and Algorithms, Contemporary Mathematics #225, R. Mullin and G. Mullen, eds., American Mathematical Society, pp.113-121, 1999. MR 99g:11145
  • 22. T. Storer, ``Cyclotomy and Difference Sets'', Markham, Chicago, 1967. MR 36:128

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11T06, 11T24, 11T22, 12Y05, 13P05

Retrieve articles in all journals with MSC (2000): 11T06, 11T24, 11T22, 12Y05, 13P05

Additional Information

Greg Stein
Affiliation: The City University of New York, 300 Jay Street, Brooklyn, New York 11201

Keywords: Finite field, factorization, cyclotomic, polynomial
Received by editor(s): December 1, 1998
Received by editor(s) in revised form: June 22, 1999
Published electronically: March 24, 2000
Additional Notes: Supported in part by PSC-CUNY Research Foundation Grant 69666-00 29
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society