Remote Access Mathematics of Computation
Green Open Access

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

Keywords: Factorization, cyclotomic fields
Article copyright: © Copyright 1989 American Mathematical Society