Computing Frobenius maps and factoring polynomials

Joachim von zur Gathen, Victor Shoup

Research output: Contribution to journalArticlepeer-review


A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degree n over Fq, the number of arithmetic operations in Fq is O((n2+nlog q). (log n)2 loglog n). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.

Original languageEnglish (US)
Pages (from-to)187-224
Number of pages38
JournalComputational Complexity
Issue number3
StatePublished - Sep 1992


  • Subject classifications: 68Q40, 11Y16, 12Y05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Computing Frobenius maps and factoring polynomials'. Together they form a unique fingerprint.

Cite this