Factoring polynomials of the form f(x^n) F_q [x]

DOI10.1016/J.FFA.2017.10.003MaRDI QIDQ1679708zbMATH OpenOpenAlexFDO

Authors Lucas Reis, F. E. Brochero Martínez

Publication date 21 November 2017

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08918

zbMATH Keywords

cyclotomic polynomialsirreducible factorsirreducible polynomial in a finite field

Mathematics Subject Classification ID

Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Finite fields (field-theoretic aspects) (12E20)

Abstract: Let $f(x)inmathbb{F}_q[x]$ be an irreducible polynomial of degree $m$ and exponent $e$, and $n$ be a positive integer such that $u_p(q-1)ge{u}_p(e)+u_p(n)$ for all $p$ prime divisor of $n$. We show a fast algorithm to determine the irreducible factors of $f(x^n)$. We also show the irreducible factors in the case when $mrad(n)$ divides $q-1$ and $mgcd(m,n)=1$. Finally, using this algorithm we split $x^n-1$ into irreducible factors, in the case when $n=2^m{p}^t$ and $q$ is a generator of the group $mathbb{Z}_{p^2}^{\ast }$.

Recommendations

• Explicit factorization of \(x^n-1\in \mathbb {F}_q[x]\)
• Further factorization of x^n-1 over a finite field. II
• Further factorization of \(x^n - 1\) over a finite field
• Factorization of x^n - 1 over the finite field F_p
• Explicit factorization of \(X^{2^m}p^n-1\) over a finite field

Cites work

• Algebraic coding theory
• Composed products and factors of cyclotomic polynomials over finite fields
• Computing Frobenius maps and factoring polynomials
• Efficient computation of roots in finite fields
• Explicit factorization of \(x^n-1\in \mathbb {F}_q[x]\)
• Explicit factorization of \(x^{2^ k}+1\) over \(F_ p\) with prime \(p\equiv 3\bmod 4\)
• Explicit factorization of \(X^{2^m}p^n-1\) over a finite field
• Explicit Factorizations of Cyclotomic and Dickson Polynomials over Finite Fields
• Factorization of the cyclotomic polynomial \(x^{2^n}+1\) over finite fields
• Fast construction of irreducible polynomials over finite fields
• scientific article; zbMATH DE number 4023423 (Why is no real title available?)
• On fast multiplication of polynomials over arbitrary algebras
• On the Chor-Rivest knapsack cryptosystem
• Subquadratic-time factoring of polynomials over finite fields

Cited in

(18)

• Ireducible quadratic factors of \(x^{(q^n+1)/2}+ax+b\) over \(\mathbb{F}_q\)
• Factorization of composed polynomials and applications
• Factorization of a class of composed polynomials
• Factoring N=p^rq^s for Large r and s
• scientific article; zbMATH DE number 3887067 (Why is no real title available?)
• Factorization of x^n - 1 over the finite field F_p
• Factorisation of x^N - q over Q
• scientific article; zbMATH DE number 3968703 (Why is no real title available?)
• scientific article; zbMATH DE number 1932275 (Why is no real title available?)
• On the prime factors of _p(M)
• Explicit factorization of \(x^n-1\in \mathbb {F}_q[x]\)
• Approximate factorization of polynomials in Z[x]
• Fixed points of the sum of divisors function on \({{\mathbb{F}}}_2[x]\)
• An infinite, two-parameter family of polynomials with factorization similar to X^m − 1
• Equal-degree factorization of binomials and trinomials over finite fields
• Closed formulas for the generators of all constacyclic codes and for the factorization of \(X^{n} - 1\), the \(n\)-th cyclotomic polynomial and every composition of the form \(f(X^n)\) over a finite field for arbitrary positive integers \(n\)
• Factorization of cyclotomic polynomial values at Mersenne prime polynomials
• On the number of irreducible factors of degree k dividing a given polynomial over GF(q)

This page was built for publication: Factoring polynomials of the form \(f(x^n) \in \mathbb{F}_q [x]\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679708)