Factoring polynomials using fewer random bits

Eric Bach, Victor Shoup

Research output: Contribution to journalArticlepeer-review


Let F be a field of q=pn elements, where p is prime. We present two new probabilisticalgorithms for factoring polynomials in F[X] that make particularly efficient use of random bits. They are easy to implement, and require no randomness beyond an initial seed whose length is proportional to the input size. The first algorithm is based on a procedure of Berlekamp; on input f in F[X] of degree d, it uses d log2p random bits and produces in polynomial time a complete factorisation of f with a failure probability of no more than 1/p(1−e)d/2. (Here ε denotes a fixed parameter between 0 and 1 that can be chosen by the implementer.) The second algorithm is based on a method of Cantor and Zassenhaus; it uses d log2q random bits and fails to find a complete factorisation with probability no more than 1/q(1−e)d/4. For both of these algorithms, the failure probability is exponentially small in the number of random bits used.

Original languageEnglish (US)
Pages (from-to)229-239
Number of pages11
JournalJournal of Symbolic Computation
Issue number3
StatePublished - 1990

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics


Dive into the research topics of 'Factoring polynomials using fewer random bits'. Together they form a unique fingerprint.

Cite this