Factoring into coprimes in essentially linear time

D.J. Bernstein

    Research output: Contribution to journalArticleAcademicpeer-review

    23 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    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 Bach, Driscoll, and Shallit. 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.
    Original languageEnglish
    Pages (from-to)1-30
    JournalJournal of Algorithms
    Volume54
    Issue number1
    DOIs
    Publication statusPublished - 2005

    Fingerprint

    Dive into the research topics of 'Factoring into coprimes in essentially linear time'. Together they form a unique fingerprint.

    Cite this