Computing Frobenius maps and factoring polynomials

Joachim Von Zur Gathen, Victor Shoup

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over Fq, the algorithm uses O((n2 + n log q) · (log n)2 log log n) arithmetic operations in Fq. 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)
Title of host publicationProceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992
PublisherAssociation for Computing Machinery
Pages97-105
Number of pages9
ISBN (Electronic)0897915119
DOIs
StatePublished - Jul 1 1992
Event24th Annual ACM Symposium on Theory of Computing, STOC 1992 - Victoria, Canada
Duration: May 4 1992May 6 1992

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129722
ISSN (Print)0737-8017

Conference

Conference24th Annual ACM Symposium on Theory of Computing, STOC 1992
CountryCanada
CityVictoria
Period5/4/925/6/92

ASJC Scopus subject areas

  • Software

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

Cite this