Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Factoring with cyclotomic polynomials


Authors: Eric Bach and Jeffrey Shallit
Journal: Math. Comp. 52 (1989), 201-219
MSC: Primary 11Y05; Secondary 12-04, 68Q40
MathSciNet review: 947467
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper discusses some new integer factoring methods involving cyclotomic polynomials.

There are several polynomials $ f(X)$ known to have the following property: given a multiple of $ f(p)$, we can quickly split any composite number that has p as a prime divisor. For example--taking $ f(X)$ to be $ X - 1$ --a multiple of $ p - 1$ will suffice to easily factor any multiple of p, using an algorithm of Pollard. Other methods (due to Guy, Williams, and Judd) make use of $ X + 1$, $ {X^2} + 1$, and $ {X^2} \pm X + 1$.

We show that one may take f to be $ {\Phi _k}$, the kth cyclotomic polynomial. In contrast to the ad hoc methods used previously, we give a universal construction based on algebraic number theory that subsumes all the above results. Assuming generalized Riemann hypotheses, the expected time to factor N (given a multiple E of $ {\Phi _k}(p)$) is bounded by a polynomial in k, $ \log E$, and $ \log N$.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 12-04, 68Q40

Retrieve articles in all journals with MSC: 11Y05, 12-04, 68Q40


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1989-0947467-1
PII: S 0025-5718(1989)0947467-1
Keywords: Factorization, cyclotomic fields
Article copyright: © Copyright 1989 American Mathematical Society



Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia