Factoring polynomials using fewer random bits

Eric Bach, Victor Shoup

Research output: Contribution to journalArticle

Abstract

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
Volume9
Issue number3
DOIs
StatePublished - 1990

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics

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

  • Cite this