A new polynomial factorization algorithm and its implementation

Victor Shoup

Research output: Contribution to journalArticlepeer-review


We consider the problem of factoring univariate polynomials over a finite field. We demonstrate that the new baby step/giant step factoring method, recently developed by Kaltofen and Shoup, can be made into a very practical algorithm. We describe an implementation of this algorithm, and present the results of empirical tests comparing this new algorithm with others. When factoring polynomials modulo large primes, the algorithm allows much larger polynomials to be factored using a reasonable amount of time and space than was previously possible. For example, this new software has been used to factor a "generic" polynomial of degree 2048 modulo a 2048-bit prime in under 12 days on a Sun SPARC-station 10, using 68 MB of main memory.

Original languageEnglish (US)
Pages (from-to)363-397
Number of pages35
JournalJournal of Symbolic Computation
Issue number4
StatePublished - Oct 1995

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics


Dive into the research topics of 'A new polynomial factorization algorithm and its implementation'. Together they form a unique fingerprint.

Cite this