Fast Polynomial Factorization and Modular Composition

Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05)

Cited In (72)

High-order lifting for polynomial Sylvester matrices
A Generalised Successive Resultants Algorithm
Improved Merlin-Arthur protocols for central problems in fine-grained complexity
An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
Interpolation by decomposable univariate polynomials
Bivariate polynomial reduction and elimination ideal over finite fields
Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities
Advancing scalability in decentralized storage: a novel approach to proof-of-replication via polynomial evaluation
Elimination ideal and bivariate resultant over finite fields
Reusable online-efficient commitments
Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE
Fast computation of hyperelliptic curve isogenies in odd characteristic
Sparse tensors and subdivision methods for finding the zero set of polynomial equations
Amortized bivariate multi-point evaluation
Solving polynomial systems over non-fields and applications to modular polynomial factoring
Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology
Univariate polynomial factorization over finite fields with large extension degree
Nearly optimal pseudorandomness from hardness
Optimal Las Vegas reduction from one-way set reconciliation to error correction
Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
Identification protocols and signature schemes based on supersingular isogeny problems
Title not available (Why is that?)
Character sums and deterministic polynomial root finding in finite fields
Amortized multi-point evaluation of multivariate polynomials
Fast algorithm of square rooting in some finite fields of odd characteristic
Algebraic Cryptanalysis of Yasuda, Takagi and Sakurai’s Signature Scheme
Sato-Tate distributions
Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields
Randomized polynomial-time root counting in prime power rings
Title not available (Why is that?)
Taking roots over high extensions of finite fields
Counting roots for polynomials modulo prime powers
Accelerated tower arithmetic
Fast computation of generic bivariate resultants
VD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private Datasets
A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
Modular composition modulo triangular sets and applications
Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
Computing isomorphisms and embeddings of finite fields
On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves
A fast algorithm for reversion of power series
Modular composition via factorization
Fast Decomposition of Polynomials with Known Galois Group
Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
On the Cipolla-Lehmer type algorithms in finite fields
On the complexity exponent of polynomial system solving
Deterministic polynomial factoring and association schemes
Deterministic root finding over finite fields using Graeffe transforms
Irreducibility of Binomials
Learning read-constant polynomials of constant degree modulo composites
Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
New Sparse Multivariate Polynomial Factorization Algorithms over Integers
Computing in degree \(2^k\)-extensions of finite fields of odd characteristic
A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
Efficiently factoring polynomials modulo \(p^4\)
Subquadratic-time algorithms for normal bases
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
Learning Read-Constant Polynomials of Constant Degree Modulo Composites
Fast arithmetic in unramified \(p\)-adic fields
Related-key security for pseudorandom functions beyond the linear barrier
Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
Fast algorithms for solving equations of degree \(\le 4\) in some finite fields
Fast amortized multi-point evaluation
Subquadratic-time factoring of polynomials over finite fields
Counting points on hyperelliptic curves of genus 2 with real models
Fast multivariate multi-point evaluation revisited
Directed evaluation
Computing the Distance between Piecewise-Linear Bivariate Functions
Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
Finding roots in \(\mathbb F_{p^n}\) with the successive resultants algorithm
Sublinear root detection and new hardness results for sparse polynomials over finite fields
Fast computation of elliptic curve isogenies in characteristic two

This page was built for publication: Fast Polynomial Factorization and Modular Composition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225172)