Factoring polynomials over finite fields
Let f be a polynomial of degree n, such that all roots of f are in the prime field \({\mathbb{F}}_ p\). The author gives an algorithm to factor f over the field \({\mathbb{F}}_ p\). This algorithm uses a given r-th non- residue in the r-th cyclotomic field \({\mathbb{F}}\) over \({\mathbb{F}}_ p\), where r is a prime divisor of n. The running time of this algorithm is polynomial in log(p) and n r. In order to find the factorization the authors construct an \(m\times m\) matrix A over \({\mathbb{F}}\), with \((m,r)=1\), such that the eigenvalues of A are all zeroes of f. The matrix A then can be used to factor f. - This method can be used for general factorization of a polynomial over an arbitrary finite field. This follows from the fact that this problem can be reduced in polynomial time to the problem of factoring a polynomial, which has all its roots in the prime field, over this prime field. The problem of finding an r-th non-residue can be solved in polynomial time, if some generalized Riemann hypothesis is true.
- Generalized riemann hypothesis and factoring polynomials over finite fields
- Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields
- Factoring polynomials over special finite fields
- scientific article; zbMATH DE number 799779
- Trading GRH for algebra: algorithms for factoring polynomials and related structures
- Factoring polynomials over global fields
- An application of factoring
- Factoring polynomials and primitive elements for special primes
- Smoothness and factoring polynomials over finite fields
- Factoring modular polynomials
- Factorization of polynomials over finite fields and characteristic sequences
- Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
- Finite nonassociative algebras obtained from skew polynomials and possible applications to \((f,\sigma,\delta)\)-codes
- Factoring polynomials over global fields. II.
- Algorithms for factoring polynomials over finite fields
- Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields
- Factoring polynomials over finite fields and stable colorings of tournaments
- Factorization of composite polynomials over finite fields
- Trading GRH for algebra: algorithms for factoring polynomials and related structures
- scientific article; zbMATH DE number 988157 (Why is no real title available?)
- Using partial smoothness of p-1 for factoring polynomials modulo p
- Generalized riemann hypothesis and factoring polynomials over finite fields
- Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields
- Multiplication of Polynomials over Finite Fields
- Explicit Bounds for Primality Testing and Related Problems
- scientific article; zbMATH DE number 4152517 (Why is no real title available?)
- Factoring with Cyclotomic Polynomials
- Searching for Primitive Roots in Finite Fields
- Factoring polynomials using binary representations of finite fields
- scientific article; zbMATH DE number 953230 (Why is no real title available?)
- Factoring a binary polynomial of degree over one million
- scientific article; zbMATH DE number 799779 (Why is no real title available?)
- Constructing nonresidues in finite fields and the extended Riemann hypothesis
- Factoring polynomials over finite fields using balance test
- scientific article; zbMATH DE number 7559413 (Why is no real title available?)
- Irreducibility and deterministic \(r\)-th root finding over finite fields
- How a nonassociative algebra reflects the properties of a skew polynomial
- Deterministic polynomial factoring and association schemes
- scientific article; zbMATH DE number 3893305 (Why is no real title available?)
- Factoring polynomials over special finite fields
- Factoring polynomials over finite fields: A survey
- On the deterministic complexity of factoring polynomials
- Factoring polynomials over local fields.
- An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
This page was built for publication: Factoring polynomials over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3795755)