Factoring polynomials modulo special primes
type: Item
instance of: scholarly article
title: Factoring polynomials modulo special primes
zbMATH Open document ID: 0694.68039
DOI: 10.1007/BF02124680
published in: Combinatorica
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 4137329
zbMATH Keywords: polynomials over finite fields
zbMATH Keywords: algorithms of factoring polynomials
zbMATH Keywords: complexity
author: Lajos Rónyai
reviewed by: Gabriele Steidl
MaRDI profile type: Publication
cites work: Algebraic coding theory
cites work: Factoring Polynomials Over Large Finite Fields
cites work: Factoring polynomials and primitive elements for special primes
cites work: Q3935355
cites work: Q3216750
cites work: On the Efficiency of Algorithms for Polynomial Factoring
cites work: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
description: scientific article; zbMATH DE number 4137329