Abstract: Let P(x) = x n + an−1x n−1 + · · · + a1x + a0 be an irreducible polynomial over Fq. In Cao, 2012, Varshamov, 1973, Lidl, 1987 the factorization of the composite polynomial P(x p − ax − δ), when a = 1 and T rFq/Fp (nb − an−1) = 0 is considered. The result of factorization of polynomial P(x p − x − δ) is a p irreducible polynomials of degree n over Fq. In this paper we propose an algorithm for factoring composite polynomial P(x p − x − δ) over Fq and give a explicit view of each factor.

Keywords: finite field, polynomial factorization, polynomial composition

ACM Classification Keywords: I.1.2. Algorithms

Link:

AN ALGORITHM FOR FACTORING COMPOSITE POLYNOMIAL P(x p − x − δ)

Sergey Abrahamyan, Knarik Kyuregyan

http://www.foibg.com/ijita/vol21/ijita21-04-p07.pdf