Computing Frobenius maps and factoring polynomials

DOI10.1007/BF01272074zbMath0778.11076OpenAlexW1998322533MaRDI QIDQ2366168

Joachim von zur Gathen, Victor Shoup

Publication date: 29 June 1993

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01272074

zbMATH Keywords

finite fieldpolynomial factorizationFrobenius mapprobabilistic algorithmdeterministic algorithm for equal-degree factorization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Algebraic number theory computations (11Y40)

Related Items

Constructing hyperelliptic curves of genus 2 suitable for cryptography, Factoring multivariate polynomials via partial differential equations, Computing special powers in finite fields, Deterministic distinct-degree factorization of polynomials over finite fields, A subquadratic algorithm for computing the $n$-th Bernoulli number, A search for Wilson primes, On the computation of minimal polynomials, cyclic vectors, and Frobenius forms, A generalisation of the Cantor-Zassenhaus algorithm, Modular composition modulo triangular sets and applications, Univariate polynomial factorization over finite fields, Factoring polynomials of the form \(f(x^n) \in \mathbb{F}_q [x\)], New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Factorization of a class of composed polynomials, Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology, Breaking SIDH in polynomial time, Orienteering with one endomorphism, Genus 2 point counting over prime fields, Univariate polynomial factorization over finite fields with large extension degree, Fast arithmetics in Artin-Schreier towers over finite fields, Interval partitions and polynomial factorization, Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic, Computing isomorphisms and embeddings of finite fields, Fast rectangular matrix multiplication and some applications, Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields, Counting curves and their projections, Pairing the volcano, Solving structured linear systems with large displacement rank, A note on Gröbner bases and Berlekamp's algorithm, Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields, Computing the bound of an Ore polynomial. Applications to factorization, Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes, Factoring polynomials over finite fields: A survey, On the deterministic complexity of factoring polynomials, Deterministic polynomial factoring and association schemes, Subquadratic-time factoring of polynomials over finite fields, Computing in degree \(2^k\)-extensions of finite fields of odd characteristic, Analysis of Rabin's irreducibility test for polynomials over finite fields, On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other, The complexity of class polynomial computation via floating point approximations, Modular composition via factorization, On a New Factorization Algorithm for Polynomials Over Finite Fields, An algorithm for Lang's theorem., Smoothness testing of polynomials over finite fields, Subquadratic-time algorithms for normal bases, Unnamed Item, CONSTRUCTIVE RECOGNITION OF NORMALIZERS OF SMALL EXTRA-SPECIAL MATRIX GROUPS, Generating Genus Two Hyperelliptic Curves over Large Characteristic Finite Fields, Identification protocols and signature schemes based on supersingular isogeny problems, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Factoring polynomials over finite fields, Fast rectangular matrix multiplication and applications, Factoring polynomials over arbitrary finite fields, Trading GRH for algebra: Algorithms for factoring polynomials and related structures, Character sums and deterministic polynomial root finding in finite fields, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, On the degrees of irreducible factors of polynomials over a finite field, Taking roots over high extensions of finite fields, Hensel lifting and bivariate polynomial factorisation over finite fields, Polynomial factorization over ${\mathbb F}_2$, Finding roots in with the successive resultants algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the deterministic complexity of factoring polynomials over finite fields
• Matrix multiplication via arithmetic progressions
• Irreducibility of multivariate polynomials
• Factoring polynomials and primitive elements for special primes
• The complexity of partial derivatives
• On fast multiplication of polynomials over arbitrary algebras
• Fast multiplication of polynomials over fields of characteristic 2
• Lower bounds for polynomial evaluation and interpolation problems
• Fast multiplication of large numbers
• Boolean circuits versus arithmetic circuits
• Constructing normal bases in finite fields
• The Computational Complexity of Continued Fractions
• Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials
• Addition requirements for matrix and transposed matrix products
• Probabilistic Algorithms in Finite Fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Subgroup Refinement Algorithms for Root Finding in $GF(q)$
• On the Efficiency of Algorithms for Polynomial Factoring
• Fast Algorithms for Manipulating Formal Power Series
• A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(p^m) of GF(p), p a Small Prime
• Factorization of Polynomials Over Finite Fields
• Factoring Polynomials Over Large Finite Fields
• ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD