Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
From MaRDI portal
Publication:5432372
DOI10.1137/S0097539704443793zbMath1210.11126OpenAlexW2090840450MaRDI QIDQ5432372
Alin Bostan, Éric Schost, Pierrick Gaudry
Publication date: 3 January 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704443793
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Factorization (11Y05)
Related Items (42)
Deterministic root finding over finite fields using Graeffe transforms ⋮ A linear-time algorithm for the orbit problem over cyclic groups ⋮ On the complexity of integer matrix multiplication ⋮ Even faster integer multiplication ⋮ A babystep-giantstep method for faster deterministic integer factorization ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ A subquadratic algorithm for computing the $n$-th Bernoulli number ⋮ A search for Wilson primes ⋮ Computing zeta functions of arithmetic schemes ⋮ A log-log speedup for exponent one-fifth deterministic integer factorisation ⋮ Improved algorithms for left factorial residues ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications ⋮ Difference integrability conditions for parameterized linear difference and differential equations ⋮ Beating binary powering for polynomial matrices ⋮ Deterministic factoring with oracles ⋮ Computing zeta functions of superelliptic curves in larger characteristic ⋮ Computing zeta functions of cyclic covers in large characteristic ⋮ Explicit Coleman integration in larger characteristic ⋮ Fast coefficient computation for algebraic power series in positive characteristic ⋮ Faster integer multiplication using short lattice vectors ⋮ Computing -series of geometrically hyperelliptic curves of genus three ⋮ Fast integer multiplication using generalized Fermat primes ⋮ Counting points on hyperelliptic curves in average polynomial time ⋮ HYPERELLIPTIC CURVES, CARTIER — MANIN MATRICES AND LEGENDRE POLYNOMIALS ⋮ Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields ⋮ Faster polynomial multiplication over finite fields using cyclotomic coefficient rings ⋮ A generic approach to searching for Jacobians ⋮ Computing zeta functions of generic projective hypersurfaces in larger characteristic ⋮ Fast multivariate multi-point evaluation revisited ⋮ A deterministic algorithm for integer factorization ⋮ An exponent one-fifth algorithm for deterministic integer factorisation ⋮ Computing Hypergeometric Functions Rigorously ⋮ Hasse–Witt and Cartier–Manin matrices: A warning and a request ⋮ A time-space tradeoff for Lehman’s deterministic integer factorization method ⋮ Variation of Néron–Severi Ranks of Reductions of K3 Surfaces ⋮ Counting points on superelliptic curves in average polynomial time ⋮ A Reduction of Integer Factorization to Modular Tetration ⋮ Faster deterministic integer factorization ⋮ Counting points on smooth plane quartics ⋮ Deterministic factorization of sums and differences of powers ⋮ Computing Hasse–Witt matrices of hyperelliptic curves in average polynomial time
Uses Software
This page was built for publication: Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
