Factoring polynomials modulo special primes (Q909466): Difference between revisions

The problem of factoring polynomials modulo large primes p with smooth p- 1 is considered. The author shows that if a primitive t-th root of unity is given for any prime t dividing p-1, then a polynomial of degree n can be factored over GF(p) in time \((\log (p)+n+S(p-1))^{0(1)}\), where S(p- 1) denotes the largest prime factor of p-1. This improves a deterministic polynomial time algorithm of \textit{J. von zur Gathen} [Theor. Comput. Sci. 52, 77-89 (1987; Zbl 0633.12009)] which uses the extended Riemann hypothesis. The presented algorithm is modified by replacing the knowledge of a primitive t-th root of unity for all primes t dividing p-1 by the construction of one such primitive root. Thereby a result of \textit{R. T. Moenck} [Math. Comput. 31, 235-250 (1977; Zbl 0348.65045)] is extended.