On the deterministic complexity of factoring polynomials over finite fields

Research output: Contribution to journalArticlepeer-review

Abstract

We present a new deterministic algorithm for factoring polynomials over Zp of degree n. We show that the worst-case running time of our algorithm is O(p 1 2(log p)2n2+∈), which is faster than the running times of previous determi nistic algorithms with respect to both n and p. We also show that our algorithm runs in polynomial time for all but at most an exponentially small fraction of the polynomials of degree n over Zp. Specifically, we prove that the fraction of polynomials of degree n over Zp for which our algorithm fails to halt in time O((log p)2n2+∈) is ((n log p)2/p). Consequently, the average-case running time of our algorithm is polynomial in n and log p.

Original languageEnglish (US)
Pages (from-to)261-267
Number of pages7
JournalInformation Processing Letters
Volume33
Issue number5
DOIs
StatePublished - Jan 10 1990

Keywords

  • Factorization
  • finite fields
  • irreducible polynomials

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'On the deterministic complexity of factoring polynomials over finite fields'. Together they form a unique fingerprint.

Cite this