Fast Polynomial Factorization and Modular Composition
From MaRDI portal
Publication:3225172
DOI10.1137/08073408XzbMath1333.11117OpenAlexW2207819601MaRDI QIDQ3225172
Christopher Umans, Kiran S. Kedlaya
Publication date: 15 March 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/08073408x
Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05) Factorization (11Y05)
Related Items (53)
Fast computation of elliptic curve isogenies in characteristic two ⋮ A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers ⋮ Deterministic root finding over finite fields using Graeffe transforms ⋮ On the Cipolla-Lehmer type algorithms in finite fields ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ On the complexity exponent of polynomial system solving ⋮ Modular composition modulo triangular sets and applications ⋮ Fast algorithms for solving equations of degree \(\le 4\) in some finite fields ⋮ Algebraic Cryptanalysis of Yasuda, Takagi and Sakurai’s Signature Scheme ⋮ Irreducibility of Binomials ⋮ An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function ⋮ New Sparse Multivariate Polynomial Factorization Algorithms over Integers ⋮ Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology ⋮ Elimination ideal and bivariate resultant over finite fields ⋮ Directed evaluation ⋮ Univariate polynomial factorization over finite fields with large extension degree ⋮ High-order lifting for polynomial Sylvester matrices ⋮ Counting roots for polynomials modulo prime powers ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Computing isomorphisms and embeddings of finite fields ⋮ Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems ⋮ Fast algorithm of square rooting in some finite fields of odd characteristic ⋮ Sato-Tate distributions ⋮ Efficiently factoring polynomials modulo \(p^4\) ⋮ Fast amortized multi-point evaluation ⋮ Related-key security for pseudorandom functions beyond the linear barrier ⋮ 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 ⋮ Deterministic polynomial factoring and association schemes ⋮ Computing in degree \(2^k\)-extensions of finite fields of odd characteristic ⋮ Fast arithmetic in unramified \(p\)-adic fields ⋮ Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants ⋮ Modular composition via factorization ⋮ Fast multivariate multi-point evaluation revisited ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ Subquadratic-time algorithms for normal bases ⋮ Computing the Distance between Piecewise-Linear Bivariate Functions ⋮ Unnamed Item ⋮ Identification protocols and signature schemes based on supersingular isogeny problems ⋮ A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ Randomized polynomial-time root counting in prime power rings ⋮ A fast algorithm for reversion of power series ⋮ Character sums and deterministic polynomial root finding in finite fields ⋮ Counting points on hyperelliptic curves of genus 2 with real models ⋮ Accelerated tower arithmetic ⋮ VD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private Datasets ⋮ Amortized multi-point evaluation of multivariate polynomials ⋮ Taking roots over high extensions of finite fields ⋮ On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves ⋮ A Generalised Successive Resultants Algorithm ⋮ Finding roots in with the successive resultants algorithm
This page was built for publication: Fast Polynomial Factorization and Modular Composition
