A new efficient factorization algorithm for polynomials over small finite fields
A new factorization algorithm for polynomials over finite fields is given. The differential equation \(y^{(p-1)}+y^ p=0\) of order \(p-1\) in the rational function field \(F_ p(x)\) is considered. It is noted \(L(y)=y^{(p-1)}+y^ p\) is a linear operator on the vector space \(F_ p(x)\) over \(F_ p\) and that the solutions of the equation with a fixed square-free denominator \(f=g_ 1\cdots g_ m\) are given by \(y=\sum^ m_{i=1} c_ i(\dot g_ i/g_ i)\) with \(c_ 1,\dots,g_ m\in F_ p\). For \(y=h/f\), \(f\) of degree \(d\), the differential equation can be written \(f^ p\Bigl({h\over f}\Bigr)^{(p-1)}=-h^ p\) and both sides are polynomials in \(x^ p\). Let \(M_ p(f)\) be the \(d\times d\) coefficient matrix of the left side. Then: Theorem: \(\text{rank}\bigl(M_ p(f)+I_ d\bigr)=d-m\). -- It follows that \(f\) is of degree \(d\) iff \(\text{rank}\bigl(M_ p(f)+I_ d\bigr)=d- 1\). The efficiency of this algorithm is considered with special attention being given to the binary case.
- A New Algorithm for Factoring Polynomials Over Finite Fields
- On a New Factorization Algorithm for Polynomials Over Finite Fields
- scientific article; zbMATH DE number 691482
- scientific article; zbMATH DE number 1273636
- An efficient algorithm for factoring polynomials over algebraic extension field
- scientific article; zbMATH DE number 1594303
- A new faster algorithm for factoring skew polynomials over finite fields
- A new polynomial factorization algorithm and its implementation
- scientific article; zbMATH DE number 1253982
- Polynomial factorization algorithms over number fields
- A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
- Factoring Polynomials over a Finite Field
- Factorization of polynomials over finite fields and characteristic sequences
- scientific article; zbMATH DE number 3882549 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3265895 (Why is no real title available?)
- Univariate polynomial factorization over finite fields
- Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
- Factorization of polynomials and some linear-algebra problems over finite fields
- A note on the factorization method of Niederreiter
- Subspaces and polynomial factorizations over finite fields
- Linear differential operators for polynomial equations
- Lifting and recombination techniques for absolute factorization
- Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields
- A new sparse Gaussian elimination algorithm and the Niederreiter linear system for trinomials over F₂
- Integers and polynomials: comparing the close cousins \(\mathbb Z\) and \(\mathbb F_q[x]\)
- Primary decomposition of zero-dimensional ideals over finite fields
- Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
- Sharp precision in Hensel lifting for bivariate polynomial factorization
- A New Algorithm for Factoring Polynomials Over Finite Fields
- scientific article; zbMATH DE number 1273636 (Why is no real title available?)
- Factoring Polynomials over Finite Fields Using Differential Equations and Normal Bases
- On a New Factorization Algorithm for Polynomials Over Finite Fields
- Subquadratic-time factoring of polynomials over finite fields
- The black-box Niederreiter algorithm and its implementation over the binary field
- Factoring multivariate polynomials via partial differential equations
- A pre-test for factoring bivariate polynomials with coefficients in \(\mathbb F_2\)
- On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic
- Factoring polynomials over finite fields: A survey
- A note on Gao's algorithm for polynomial factorization
- Algebraic solutions of linear differential equations: an arithmetic approach
This page was built for publication: A new efficient factorization algorithm for polynomials over small finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366271)
