Deterministic analysis of aleatoric methods of polynomial factorization over finite fields

DOI10.1006/JNTH.1994.1024MaRDI QIDQ1323866zbMATH OpenOpenAlexFDO

Authors M. Rothstein, H. Zassenhaus

Publication date 15 December 1994

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jnth.1994.1024

zbMATH Keywords

Cantor-Zassenhaus algorithmcomplexitydeterministic factorization algorithmfinite fieldmonic polynomials

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Review text

This paper deals with the problem of factoring a monic polynomial \(f\) over a finite field \(GF(q)\) into a product of irreducible monic polynomials over \(GF(q)\). By either the method of \textit{E. R. Berlekamp} [Factoring polynomials over large finite fields, Math. Comput. 24 (1970), 713-735 (1971; Zbl 0247.12014)] or the method of \textit{D. G. Cantor} and \textit{H. Zassenhaus} [Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)] this problem is reduced to the problem of finding the roots of a polynomial for which it is known that the polynomial is a product of distinct linear factors over \(GF(q)\). Thus without loss of generality it may be assumed that \(f= \prod_{i=1}^ n (t-\xi_ i)\), where \(\xi_ 1, \xi_ 2, \dots, \xi_ n\) are distinct nonzero elements of \(GF(q)\). The methods of Berlekamp and Cantor-Zassenhaus are both probabilistic methods. In the paper under review the authors propose a deterministic version of the Cantor-Zassenhaus algorithm. It is conjectured that this algorithm has complexity \(O(n^ 4 \log p)\), where \(n= \text{degree} (f)\) and \(p\) is the characteristic of \(GF(q)\). A combinatorial problem is formulated whose solution would imply the truth of this conjecture. The authors also present a new deterministic factorization algorithm that requires knowledge of a primitive root of \(GF(q)\).

Recommendations

• On a New Factorization Algorithm for Polynomials Over Finite Fields
• On the deterministic complexity of factoring polynomials
• Factoring polynomials over arbitrary finite fields
• scientific article; zbMATH DE number 3880116
• Computing Frobenius maps and factoring polynomials

Cited in

(12)

• Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
• A verified implementation of the Berlekamp-Zassenhaus factorization algorithm
• Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
• Improving the Berlekamp algorithm for binomials \(x^{n}-a\)
• scientific article; zbMATH DE number 3872677 (Why is no real title available?)
• scientific article; zbMATH DE number 4065121 (Why is no real title available?)
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(p^m) of GF(p), p a Small Prime
• scientific article; zbMATH DE number 691482 (Why is no real title available?)
• Subquadratic-time factoring of polynomials over finite fields
• Deterministic root finding in finite fields
• Factoring polynomials over finite fields: A survey

This page was built for publication: Deterministic analysis of aleatoric methods of polynomial factorization over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323866)