×

Factoring into coprimes in essentially linear time. (English) Zbl 1134.11352

Summary: Let \(S\) be a finite set of positive integers. A “coprime base for \(S\)” means a set \(P\) of positive integers such that (1) each element of \(P\) is coprime to every other element of \(P\) and (2) each element of \(S\) is a product of powers of elements of \(P\). There is a natural coprime base for \(S\). This paper introduces an algorithm that computes the natural coprime base for \(S\) in essentially linear time. The best previous result was a quadratic-time algorithm of E. Bach, J. Driscoll and J. Shallit [J. Algorithms 15, No. 2, 199–222 (1993; Zbl 0784.11058)]. This paper also shows how to factor \(S\) into elements of \(P\) in essentially linear time. The algorithms use solely multiplication, exact division, gcd, and equality testing, so they apply to any free commutative monoid with fast algorithms for those four operations; for example, given a finite set \(S\) of monic polynomials over a finite field, the algorithms factor \(S\) into coprimes in essentially linear time. These algorithms can be used as a substitute for prime factorization in many applications.

MSC:

11Y05 Factorization
68W30 Symbolic computation and algebraic computation
68W40 Analysis of algorithms
11Y16 Number-theoretic algorithms; complexity

Citations:

Zbl 0784.11058
PDFBibTeX XMLCite
Full Text: DOI