Factoring polynomials using binary representations of finite fields
- 1 January 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 43 (1), 147-153
- https://doi.org/10.1109/18.567667
Abstract
The factorization of polynomials over finite fields is considered. A new deterministic algorithm is proposed that solves the equal-degree factorization problem by combining Berlekamp's (1970) trace algorithm iterative method with the concept of binary representations of finite fields. The interesting aspects of the new algorithm are its simple structure, the easy proof of its correctness, and its efficiency when an efficient realization of the mapping from the finite field to a binary representation is known. Some results about binary representations of finite fields are derived to show that the new factoring algorithm is also nonasymptotically efficient for every finite field. The only practical drawback may be the precomputation of some constants needed in the binary representation, but several suggestions are given to improve this when more about the finite field is knownKeywords
This publication has 9 references indexed in Scilit:
- Smoothness and factoring polynomials over finite fieldsInformation Processing Letters, 1991
- Factoring polynomials modulo special primesCombinatorica, 1989
- Some computational aspects of root finding in GF(qm)Lecture Notes in Computer Science, 1989
- Factoring polynomials and primitive elements for special primesTheoretical Computer Science, 1987
- Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomialsIEEE Transactions on Information Theory, 1983
- On the power of straight- line computations in finite fieldsIEEE Transactions on Information Theory, 1982
- An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)IEEE Transactions on Information Theory, 1978
- Berechnung und programm. IActa Informatica, 1972
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970