Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

Abstract:

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
Email: gregstein@member.ams.org

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01233-3
PII: S 0025-5718(00)01233-3
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