Roots and Polynomial Factorization

• Square root: Tonelli-Shanks method for $\mbox{\rm GF}(p)$
• n-th root
• One root of a polynomial; All roots root of a polynomial
• Polynomial factorization: Small field Berlekamp, large field Berlekamp
• Polynomial factorization: Shoup algorithm
• Construction of a splitting field
• Factorisation over splitting field

Factorization of polynomials over $\mbox{\rm GF}(q)$ for large q uses Shoup's algorithm. On a 64-bit 200MHz SGI Origin 2000, the n=2048 polynomial from the von zur Gathen challenge benchmarks (of degree 2048 with sparse coefficients modulo a 2050-bit prime) is factored by Magma V2.7 in about 18.8 hours and the n=3000 polynomial from the same benchmarks (of degree 3000 with sparse coefficients modulo a 3002-bit prime) is factored by Magma V2.7 in about 75.8 hours. Also, the n=2048 polynomial from the Shoup challenge benchmarks (of degree 2048 with dense coefficients modulo a 2048-bit prime) is factored by Magma V2.7 in about 36.0 hours on the same machine.