TY - GEN

T1 - Computing Frobenius maps and factoring polynomials

AU - Von Zur Gathen, Joachim

AU - Shoup, Victor

N1 - Publisher Copyright:
© 1992 ACM.

PY - 1992/7/1

Y1 - 1992/7/1

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

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

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

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

U2 - 10.1145/129712.129722

DO - 10.1145/129712.129722

M3 - Conference contribution

AN - SCOPUS:0026999432

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 97

EP - 105

BT - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992

PB - Association for Computing Machinery

T2 - 24th Annual ACM Symposium on Theory of Computing, STOC 1992

Y2 - 4 May 1992 through 6 May 1992

ER -