Subquadratic-time factoring of polynomials over finite fields

DOI10.1090/S0025-5718-98-00944-2zbMath0902.11053OpenAlexW1979366382MaRDI QIDQ4396457

Publication date: 14 June 1998

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0025-5718-98-00944-2

zbMATH Keywords

finite fields probabilistic algorithms univariate polynomials factoring subquadratic complexity baby step/giant step

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Finite fields (field-theoretic aspects) (12E20) Polynomials, factorization in commutative rings (13P05)

Related Items

Preimages of $p$-linearized polynomials over $\mathbb{F}_p$, Constructing irreducible polynomials over finite fields, Factoring multivariate polynomials via partial differential equations, On design of circuits of logarithmic depth for inversion in finite fields, Deterministic distinct-degree factorization of polynomials over finite fields, Modular equations for hyperelliptic curves, Complexity of computation in finite fields, Factoring polynomials of the form $f(x^n) \in \mathbb{F}_q [x$], Skew differential Goppa codes and their application to McEliece cryptosystem, Elimination ideal and bivariate resultant over finite fields, Univariate polynomial factorization over finite fields with large extension degree, Interval partitions and polynomial factorization, Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic, Computing cardinalities of -curve reductions over finite fields, Computing isomorphisms and embeddings of finite fields, Fast rectangular matrix multiplication and some applications, Fast computation of special resultants, Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields, A new faster algorithm for factoring skew polynomials over finite fields, A note on Gröbner bases and Berlekamp's algorithm, Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields, Fast computation of generic bivariate resultants, 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, Fast algorithms for computing isogenies between elliptic curves, Deterministic polynomial factoring and association schemes, Explicit computation of isomorphisms between finite fields, Factoring Polynomials over Local Fields II, On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other, Factoring polynomials over local fields., The black-box Niederreiter algorithm and its implementation over the binary field, Modular composition via factorization, Subquadratic-time algorithms for normal bases, Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Algorithm for calculating the roots of polynomials with coefficients in the ring of polynomials over an arbitrary integral domain, 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, Algorithms for exponentiation in finite fields, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules., 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