Subquadratic-time factoring of polynomials over finite fields

Erich Kaltofen, Victor Shoup

Research output: Contribution to journalArticle

Abstract

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time O(n1.815). Previous algorithms required time θ(n2+0(1)). The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n over the finite field double-struck Fq with q elements, the algorithms use O(n1.815 log q) arithmetic operations in double-struck Fq. The new "baby step/giant step" techniques used in our a gorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-tirne methods for manipulating normal bases of finite fields.

Original languageEnglish (US)
Pages (from-to)1179-1197
Number of pages19
JournalMathematics of Computation
Volume67
Issue number223
DOIs
StatePublished - Jul 1998

Keywords

  • Factoring
  • Finite fields
  • Normal bases
  • Polynomials
  • Randomized algorithms

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Subquadratic-time factoring of polynomials over finite fields'. Together they form a unique fingerprint.

  • Cite this