Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
From MaRDI portal
Publication:5432372
DOI10.1137/S0097539704443793zbMath1210.11126MaRDI 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
68Q25: Analysis of algorithms and problem complexity
11Y16: Number-theoretic algorithms; complexity
11Y05: Factorization
Related Items
Fast integer multiplication using generalized Fermat primes, Computing zeta functions of generic projective hypersurfaces in larger characteristic, An exponent one-fifth algorithm for deterministic integer factorisation, Computing Hypergeometric Functions Rigorously, A time-space tradeoff for Lehman’s deterministic integer factorization method, Polynomial Multiplication over Finite Fields in Time \( O(n \log n \), A log-log speedup for exponent one-fifth deterministic integer factorisation, HYPERELLIPTIC CURVES, CARTIER — MANIN MATRICES AND LEGENDRE POLYNOMIALS, Hasse–Witt and Cartier–Manin matrices: A warning and a request, Deterministic factorization of sums and differences of powers, 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, Beating binary powering for polynomial matrices, Deterministic factoring with oracles, 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, Deterministic root finding over finite fields using Graeffe transforms, A linear-time algorithm for the orbit problem over cyclic groups, Even faster integer multiplication, Difference integrability conditions for parameterized linear difference and differential equations, Computing zeta functions of superelliptic curves in larger characteristic, On the complexity of integer matrix multiplication, Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields, Counting points on smooth plane quartics, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, Fast multivariate multi-point evaluation revisited, Counting points on hyperelliptic curves in average polynomial time, 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, A deterministic algorithm for integer factorization, Faster deterministic integer factorization, Computing Hasse–Witt matrices of hyperelliptic curves in average polynomial time, Computing -series of geometrically hyperelliptic curves of genus three, A generic approach to searching for Jacobians, A babystep-giantstep method for faster deterministic integer factorization, A subquadratic algorithm for computing the $n$-th Bernoulli number, A search for Wilson primes, Computing zeta functions of arithmetic schemes
Uses Software
