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 Free Access

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?)

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