Faster Integer Multiplication
From MaRDI portal
Publication:3575156
DOI10.1137/070711761zbMath1192.68926OpenAlexW2087957223MaRDI QIDQ3575156
Publication date: 7 July 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/36d67d9382584182817484cba7f0b77b9af9be07
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30)
Related Items (66)
A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line ⋮ Tensors in computations ⋮ On computation of the Bessel function by summing up the series ⋮ Tighter Fourier Transform Lower Bounds ⋮ On the complexity of integer matrix multiplication ⋮ Even faster integer multiplication ⋮ Efficient Computation of the Characteristic Polynomial of a Threshold Graph ⋮ Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem ⋮ A babystep-giantstep method for faster deterministic integer factorization ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ Bounded-degree factors of lacunary multivariate polynomials ⋮ A self-tester for linear functions over the integers with an elementary proof of correctness ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ Squeezing Feasibility ⋮ A search for Wilson primes ⋮ Dirichlet’s proof of the three-square theorem: An algorithmic perspective ⋮ A survey on delegated computation ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ On a fast algorithm for computing the Fourier transform ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications ⋮ On the universality of product for classes of linear functions of two variables ⋮ On the computational complexity of compressed power series ⋮ Nearly optimal refinement of real roots of a univariate polynomial ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ Faster integer multiplication using short lattice vectors ⋮ On the complexity of inverting integer and polynomial matrices ⋮ Fast evaluation algorithms for elementary algebraic and inverse functions using the FEE method ⋮ Efficient authentication from hard learning problems ⋮ A fast algorithm for computing the digamma function ⋮ On the complexity of regular-grammars with integer attributes ⋮ The numerical solution of fractional integral equations via orthogonal polynomials in fractional powers ⋮ Fast structured matrix computations: tensor rank and Cohn-Umans method ⋮ Computing -series of geometrically hyperelliptic curves of genus three ⋮ Fast integer multiplication using generalized Fermat primes ⋮ Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ Fast algorithm of square rooting in some finite fields of odd characteristic ⋮ Fast computation of the number of solutions to \(x_1^2 + \cdots + x_k^2 \equiv \lambda \pmod{n}\) ⋮ New width parameters for SAT and \#SAT ⋮ Efficient computation of the characteristic polynomial of a threshold graph ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Backtracking-assisted multiplication ⋮ Extending partial representations of proper and unit interval graphs ⋮ Efficient computation of the characteristic polynomial of a tree and related tasks ⋮ On the complexity of computing with planar algebraic curves ⋮ A simple and fast method for computing the Poisson binomial distribution function ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Faster polynomial multiplication over finite fields using cyclotomic coefficient rings ⋮ Faster integer multiplication using plain vanilla FFT primes ⋮ On the complexity of Fibonacci coding ⋮ A framework for deterministic primality proving using elliptic curves with complex multiplication ⋮ Computing the depth distribution of a set of boxes ⋮ Unnamed Item ⋮ Lower Bounds for Multiplication via Network Coding ⋮ The complexity of solving low degree equations over ring of integers and residue rings ⋮ Unnamed Item ⋮ Computing persistent homology with various coefficient fields in a single pass ⋮ On the Complexity of Bounded Context Switching. ⋮ Linear differential equations as a data structure ⋮ Counting composites with two strong liars ⋮ Unnamed Item ⋮ A faster tree-decomposition based algorithm for counting linear extensions ⋮ On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average ⋮ Faster deterministic integer factorization ⋮ Deterministic factorization of sums and differences of powers
This page was built for publication: Faster Integer Multiplication
