TY - GEN
T1 - Computing Frobenius maps and factoring polynomials
AU - Von Zur Gathen, Joachim
AU - Shoup, Victor
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 -