Univariate polynomial factorization over finite fields
From MaRDI portal
Publication:1127311
This paper is a tutorial introduction to univariate polynomial factorization over finite fields. The authors recall the classical methods that induced most factorization algorithms (Berlekamp's and the Cantor-Zassenhaus ones) and some refinements which can be applied to these methods. Explicit algorithms are presented in a form suitable for almost immediate implementation. They give a detailed description of an efficient implementation of the Cantor-Zassenhaus algorithm used in the release 2 of the Axiom computer algebra system.
Recommendations
Cites work
- A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
- A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(pm) of GF(p), p a Small Prime
- A Generalized Class of Polynomials that are Hard to Factor
- A geometric approach to root finding in GT(q/sup m/)
- A knapsack-type public key cryptosystem based on arithmetic in finite fields
- A method for obtaining digital signatures and public-key cryptosystems
- A New Algorithm for Factoring Polynomials Over Finite Fields
- A new efficient factorization algorithm for polynomials over small finite fields
- A new polynomial factorization algorithm and its implementation
- A note on square roots in finite fields
- A Remark on the Hensel Factorization Method
- A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
- Algebraic algorithms in GF(q)
- Algorithms related to the decomposition of polynomials
- An Acceleration of the Niederreiter Factorization Algorithm in Characteristic 2
- An analog to the discriminant over fields of characteristic two
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- Arithmetic in a Finite Field
- Arithmetic of finite fields
- Computable Algebra, General Theory and Theory of Computable Fields
- Computational problems in the theory of finite fields
- Computer Algebra of Polynomials and Rational Functions
- Computing Frobenius maps and factoring polynomials
- Computing Gretest Common Divisors and Factorizations in Quadratic Number Fields
- Computing in GF(q)
- Computing roots of polynomials on vector processing machines
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
- Constructions in Algebra
- Counting irreducible factors of polynomials over a finite field
- Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme
- Distinct Degree Factorizations for Polynomials over a Finite Field
- Effective procedures in field theory
- Factoring of \(x^ n -1\) and orthogonalization over finite fields of characteristic 2
- Factoring polynomials and primitive elements for special primes
- Factoring polynomials in finite fields: An application of Lang-Weil to a problem in graph theory
- Factoring polynomials modulo special primes
- Factoring Polynomials over a Finite Field
- Factoring Polynomials over Finite Fields Using Differential Equations and Normal Bases
- Factoring Polynomials Over Large Finite Fields
- Factorization of polynomials and some linear-algebra problems over finite fields
- Factorization of polynomials over a finite field and the solution of systems of algebraic equations
- Factorization of polynomials over finite fields
- Factorization of Polynomials Over Finite Fields
- Factorization of polynomials over finite fields and characteristic sequences
- Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields
- Factorization of univariate polynomials
- Factorization over a finite field \(\mathbb F_{p^n}\) of the composite polynomials \(f\left(X^{p^r}-aX\right)\) where \(f(X)\) is an irreducible polynomial in \(\mathbb F_{p^n}(X)\)
- Fast construction of irreducible polynomials over finite fields
- Finding irreducible and primitive polynomials
- Finding Isomorphisms Between Finite Fields
- Finding the number of factors of a polynomial
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
- Galois Groups and Factoring Polynomials over Finite Fields
- Hiding information and signatures in trapdoor knapsacks
- How to share a secret
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 3880116 (Why is no real title available?)
- scientific article; zbMATH DE number 4152523 (Why is no real title available?)
- scientific article; zbMATH DE number 3822792 (Why is no real title available?)
- scientific article; zbMATH DE number 3823145 (Why is no real title available?)
- scientific article; zbMATH DE number 3910467 (Why is no real title available?)
- scientific article; zbMATH DE number 4002212 (Why is no real title available?)
- scientific article; zbMATH DE number 4023423 (Why is no real title available?)
- scientific article; zbMATH DE number 4035950 (Why is no real title available?)
- scientific article; zbMATH DE number 4065121 (Why is no real title available?)
- scientific article; zbMATH DE number 4069025 (Why is no real title available?)
- scientific article; zbMATH DE number 4070838 (Why is no real title available?)
- scientific article; zbMATH DE number 4094800 (Why is no real title available?)
- scientific article; zbMATH DE number 3658967 (Why is no real title available?)
- scientific article; zbMATH DE number 3717441 (Why is no real title available?)
- scientific article; zbMATH DE number 3763833 (Why is no real title available?)
- scientific article; zbMATH DE number 3785000 (Why is no real title available?)
- scientific article; zbMATH DE number 3785004 (Why is no real title available?)
- scientific article; zbMATH DE number 3785035 (Why is no real title available?)
- scientific article; zbMATH DE number 15339 (Why is no real title available?)
- scientific article; zbMATH DE number 45834 (Why is no real title available?)
- scientific article; zbMATH DE number 53946 (Why is no real title available?)
- scientific article; zbMATH DE number 107769 (Why is no real title available?)
- scientific article; zbMATH DE number 108109 (Why is no real title available?)
- scientific article; zbMATH DE number 3465417 (Why is no real title available?)
- scientific article; zbMATH DE number 3480679 (Why is no real title available?)
- scientific article; zbMATH DE number 3481857 (Why is no real title available?)
- scientific article; zbMATH DE number 3526799 (Why is no real title available?)
- scientific article; zbMATH DE number 3568023 (Why is no real title available?)
- scientific article; zbMATH DE number 3597592 (Why is no real title available?)
- scientific article; zbMATH DE number 4127340 (Why is no real title available?)
- scientific article; zbMATH DE number 1194925 (Why is no real title available?)
- scientific article; zbMATH DE number 1263398 (Why is no real title available?)
- scientific article; zbMATH DE number 1273636 (Why is no real title available?)
- scientific article; zbMATH DE number 1273637 (Why is no real title available?)
- scientific article; zbMATH DE number 1273638 (Why is no real title available?)
- scientific article; zbMATH DE number 481965 (Why is no real title available?)
- scientific article; zbMATH DE number 691468 (Why is no real title available?)
- scientific article; zbMATH DE number 691475 (Why is no real title available?)
- scientific article; zbMATH DE number 691482 (Why is no real title available?)
- scientific article; zbMATH DE number 2168577 (Why is no real title available?)
- scientific article; zbMATH DE number 220087 (Why is no real title available?)
- scientific article; zbMATH DE number 3450338 (Why is no real title available?)
- scientific article; zbMATH DE number 910950 (Why is no real title available?)
- scientific article; zbMATH DE number 918133 (Why is no real title available?)
- scientific article; zbMATH DE number 3230409 (Why is no real title available?)
- scientific article; zbMATH DE number 3235414 (Why is no real title available?)
- scientific article; zbMATH DE number 3265895 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- scientific article; zbMATH DE number 3318360 (Why is no real title available?)
- scientific article; zbMATH DE number 3412760 (Why is no real title available?)
- scientific article; zbMATH DE number 967590 (Why is no real title available?)
- Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials
- Irreducibility Testing and Factorization of Polynomials
- Multiplication of Polynomials over Finite Fields
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- New directions in cryptography
- Note on cubics over GF(2ⁿ) and GF(3ⁿ)
- On a New Factorization Algorithm for Polynomials Over Finite Fields
- On arithmetical algorithms over finite fields
- On fast multiplication of polynomials over arbitrary algebras
- On Hensel factorization. I
- On Polynomial Factorization Over Finite Fields
- On the Chor-Rivest knapsack cryptosystem
- On the computational power of pushdown automata
- On the continued fraction and Berlekamp's algorithm (Corresp.)
- On the deterministic complexity of factoring polynomials over finite fields
- On the Distribution of Quadratic Residues and Nonresidues Modulo a Prime Number
- On the Efficiency of a Polynomial Irreducibility Test
- On the Efficiency of Algorithms for Polynomial Factoring
- On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.)
- On the factorization of polynomials
- On the Quadratic Character of a Polynomial
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
- On the solution of algebraic equations over finite fields
- Primitive Polynomials Over Finite Fields
- Probabilistic Algorithms in Finite Fields
- Searching for Primitive Roots in Finite Fields
- Separable algebras over commutative rings
- Smoothness and factoring polynomials over finite fields
- Solving equations in finite fields and some results concerning the structure of GF(p/sup m/)
- Solving sparse linear equations over finite fields
- Square-free algorithms in positive characteristic
- Statistics on factoring polynomials mod p and p-adically
- The Chinese remainder theorem
- The Factorization of the Cyclotomic Polynomials mod p
- Un Algorithme De Construction Des Idempotents Primitifs D'Ideaux D'Algebres Sur Fq
- When Does a Polynomial Over a Finite Field Permute the Elements of the Field?
Cited in
(17)- A generalisation of the Cantor-Zassenhaus algorithm
- Factoring polynomials over arbitrary finite fields
- Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
- Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic
- A note on Gröbner bases and Berlekamp's algorithm
- Improvements on the Cantor-Zassenhaus factorization algorithm.
- scientific article; zbMATH DE number 3880116 (Why is no real title available?)
- scientific article; zbMATH DE number 4043916 (Why is no real title available?)
- scientific article; zbMATH DE number 1273637 (Why is no real title available?)
- scientific article; zbMATH DE number 1273638 (Why is no real title available?)
- Single-factor lifting and factorization of polynomials over local fields
- scientific article; zbMATH DE number 2077079 (Why is no real title available?)
- scientific article; zbMATH DE number 1519867 (Why is no real title available?)
- A Graph-Based Unified Technique for Computing and Representing Coefficients over Finite Fields
- scientific article; zbMATH DE number 922258 (Why is no real title available?)
- Factoring polynomials over finite fields: A survey
- Fast rectangular matrix multiplication and some applications
This page was built for publication: Univariate polynomial factorization over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127311)
