Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials

Paul Camion

IEEE Transactions on Information Theory · 1983 · 31 citations · 5 references

Concepts

Abstract

Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f(x)\in {\bf F}_{q}[X]</tex> be a polynomial with simple roots to be factored. The so-called Berlekamp subalgebra <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</tex> spanned over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">{\bf F}_{q}</tex> by the idempotents of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A={\bf F}_{q}[X]/(f(X))</tex> is considered. An exponential technique introduced earlier is based upon taking elements from B at random and enables us to obtain idempotents and, from that, the factors of f(X). This algorithm is speeded up in three ways. The concept of a separating subset of B is introduced and the McEliece operator mapping A onto B is used to construct a small separating set. {\em Factoring} subsets of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">{\bf F}_{q}</tex> were defined and investigated previously. The algorithm and these subsets are used together with a process introduced by F. J. McWilliams for the rapid construction of primitive idempotents. Finally, an algorithm is introduced for constructing irreducible polynomials of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">{\bf F}_{q}[X]</tex> of degree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</tex> , for large values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</tex> , in which the most expensive operation is the Euclidian algorithm applied to two polynomials of degree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2d</tex> .

References

5