Factorization of polynomials over finite fields and characteristic sequences (Q1322768)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Factorization of polynomials over finite fields and characteristic sequences |
scientific article |
Statements
Factorization of polynomials over finite fields and characteristic sequences (English)
0 references
20 October 1994
0 references
The first author has recently introduced a new algorithm for the efficient factorization of polynomials over finite fields [Appl. Algebra Eng. Commun. Comput. 4, 81-87 (1993; Zbl 0776.11070)]. Several researchers have generalized the algorithm and suggested techniques for speeding it up. It is noted there are two techniques for generalizing the algorithm, by using either normal bases of field extensions or by applying Hasse-Teichmüller derivatives. This work considers the second techniques using derivatives and shows, in particular, that the linearization step of the general factorization algorithm using these derivatives is feasible for arbitrary finite fields. A general principle for linearizing the factorizing problem for polynomials is introduced which is derived from a certain decimation operator on sequences. The linearization using derivatives is an application of this principle.
0 references
polynomial factorization
0 references
linear recurring sequences
0 references
Hasse-Teichmüller derivatives
0 references
linearization
0 references
factorization algorithm
0 references
finite fields
0 references