Computing Frobenius maps and factoring polynomials

Joachim von zur Gathen; Victor Shoup

doi:10.1007/BF01272074

Computing Frobenius maps and factoring polynomials

Joachim von zur Gathen, Victor Shoup

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degree n over F_q, the number of arithmetic operations in F_q is O((n²+nlog q). (log n)² 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 language	English (US)
Pages (from-to)	187-224
Number of pages	38
Journal	Computational Complexity
Volume	2
Issue number	3
DOIs	https://doi.org/10.1007/BF01272074
State	Published - Sep 1992

Keywords

Subject classifications: 68Q40, 11Y16, 12Y05

ASJC Scopus subject areas

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1007/BF01272074

Cite this

@article{521c82ecf38949a8b370f982d1fb01d8,

title = "Computing Frobenius maps and factoring polynomials",

abstract = "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.",

keywords = "Subject classifications: 68Q40, 11Y16, 12Y05",

author = "{von zur Gathen}, Joachim and Victor Shoup",

year = "1992",

month = sep,

doi = "10.1007/BF01272074",

language = "English (US)",

volume = "2",

pages = "187--224",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "3",

}

TY - JOUR

T1 - Computing Frobenius maps and factoring polynomials

AU - von zur Gathen, Joachim

AU - Shoup, Victor

PY - 1992/9

Y1 - 1992/9

N2 - 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.

AB - 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.

KW - Subject classifications: 68Q40, 11Y16, 12Y05

UR - http://www.scopus.com/inward/record.url?scp=0001605828&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001605828&partnerID=8YFLogxK

U2 - 10.1007/BF01272074

DO - 10.1007/BF01272074

M3 - Article

AN - SCOPUS:0001605828

SN - 1016-3328

VL - 2

SP - 187

EP - 224

JO - Computational Complexity

JF - Computational Complexity

IS - 3

ER -

Computing Frobenius maps and factoring polynomials

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this