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




Related Items (53)

Fast computation of elliptic curve isogenies in characteristic twoA softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integersDeterministic root finding over finite fields using Graeffe transformsOn the Cipolla-Lehmer type algorithms in finite fieldsRoot repulsion and faster solving for very sparse polynomials over \(p\)-adic fieldsOn the complexity exponent of polynomial system solvingModular composition modulo triangular sets and applicationsFast algorithms for solving equations of degree \(\le 4\) in some finite fieldsAlgebraic Cryptanalysis of Yasuda, Takagi and Sakurai’s Signature SchemeIrreducibility of BinomialsAn effective description of the roots of bivariates mod pk and the related Igusa’s local zeta functionNew Sparse Multivariate Polynomial Factorization Algorithms over IntegersComputing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline CohomologyElimination ideal and bivariate resultant over finite fieldsDirected evaluationUnivariate polynomial factorization over finite fields with large extension degreeHigh-order lifting for polynomial Sylvester matricesCounting roots for polynomials modulo prime powersImproved Merlin-Arthur protocols for central problems in fine-grained complexityComputing isomorphisms and embeddings of finite fieldsEffective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systemsFast algorithm of square rooting in some finite fields of odd characteristicSato-Tate distributionsEfficiently factoring polynomials modulo \(p^4\)Fast amortized multi-point evaluationRelated-key security for pseudorandom functions beyond the linear barrierDrinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fieldsFast computation of generic bivariate resultantsDeterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemesDeterministic polynomial factoring and association schemesComputing in degree \(2^k\)-extensions of finite fields of odd characteristicFast arithmetic in unramified \(p\)-adic fieldsGeneralized Kakeya sets for polynomial evaluation and faster computation of fermionantsModular composition via factorizationFast multivariate multi-point evaluation revisitedOptimal Las Vegas reduction from one-way set reconciliation to error correctionSubquadratic-time algorithms for normal basesComputing the Distance between Piecewise-Linear Bivariate FunctionsUnnamed ItemIdentification protocols and signature schemes based on supersingular isogeny problemsA promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and densitySublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite FieldsRandomized polynomial-time root counting in prime power ringsA fast algorithm for reversion of power seriesCharacter sums and deterministic polynomial root finding in finite fieldsCounting points on hyperelliptic curves of genus 2 with real modelsAccelerated tower arithmeticVD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private DatasetsAmortized multi-point evaluation of multivariate polynomialsTaking roots over high extensions of finite fieldsOn the decisional Diffie-Hellman problem for class group actions on oriented elliptic curvesA Generalised Successive Resultants AlgorithmFinding roots in with the successive resultants algorithm




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