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
    0 references
    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
    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
    0 references
    0 references