No label defined (Q3801677)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4069025
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4069025

      Statements

      0 references
      0 references
      1988
      0 references
      FAST16
      0 references
      factorizing square-free polynomials over large, finite, prime fields
      0 references
      algorithm
      0 references
      [For the entire collection see Zbl 0642.00029.] The authors consider the problem of factorizing square-free polynomials over large, finite, prime fields. They give a categorization of the methods used until now for this problem. These ideas are used and the authors present a new algorithm. They compare the performance of this algorithm with that of Macsyma. The result is that their algorithm is faster. Let \(f\in {\mathbb{F}}_ p[X]\) be a square-free polynomial. The algorithm first searches for a factorization of the f into a product \(f_{(r)}g\), such that \(f_{(r)}\) consists of all irreducible factors of f whose degrees divide a certain integer r. This is done by taking the greatest common divisor of f and \(x^{p\quad j}-x\) for certain j. In the second step the authors try to find a factorization of \(f_{(r)}\) into products of polynomials, such that each of them is a product of irreducible polynomials of the same degree. Finally these parts are factorized, using some norm function. The presented algorithm is probabilistic in the sense that several tries have to be made in each step. The authors provide average numbers of how often such tries have to be made.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references