Factoring polynomials of the form f(xⁿ)∈ Fq[x]

الأصل · EN

Let f(x)∈ Fq[x] be an irreducible polynomial of degree m and exponent e, and n be a positive integer such that νₚ(q-1)≥ νₚ(e)+νₚ(n) for all p prime divisor of n. We show a fast algorithm to determine the irreducible factors of f(xⁿ). We also show the irreducible factors in the case when rad(n) divides q-1 and gcd(m, n)=1. Finally, using this algorithm we split xⁿ-1 into irreducible factors, in the case when n=2ᵐpᵗ and q is a generator of the group Zₚ₂*.