Fast multiplication of large numbers
From MaRDI portal
Publication:2548172
DOI10.1007/BF02242355zbMath0223.68007OpenAlexW2083368929WikidataQ56067772 ScholiaQ56067772MaRDI QIDQ2548172
Volker Strassen, Arnold Schönhage
Publication date: 1971
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02242355
Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Numerical methods for wavelets (65T60) Mathematical problems of computer architecture (68M07)
Related Items
A unified FFT-based approach to maximum assignment problems related to transitive finite group actions, Computation of integral bases, Explicit primality criteria for \(h \cdot 2^n \pm 1\), A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic, An improved deterministic algorithm for generating different many-element random samples, Variants of the Selberg sieve, and bounded intervals containing many primes, A fast algorithm for computing large Fibonacci numbers, On the complexity of integer matrix multiplication, Even faster integer multiplication, Homomorphic AES evaluation using the modified LTV scheme, Optimal 2-constraint satisfaction via sum-product algorithms, A fast numerical algorithm for the composition of power series with complex coefficients, Factoring polynomials and primitive elements for special primes, Perfect power testing, Time-space efficient algorithms for computing convolutions and related problems, Quantum mechanical algorithm for solving quadratic residue equation, Algorithms for monitoring real-time properties, An algorithm for computing the factor ring of an ideal in Dedekind domain with finite rank, Feedback shift registers, 2-adic span, and combiners with memory, On the parameterized complexity of b-\textsc{chromatic number}, The bit-cost of some algorithms for the solution of linear systems, Carryless addition, Efficient parallel circuits and algorithms for division, Fast arithmetic with general Gauß periods, Fast fraction-free triangularization of Bézoutians with applications to sub-resultant chain computation, Complexity of computation in finite fields, Fast matrix multiplication is stable, Cauchy index computation, Queries with arithmetical constraints, Algorithmic theory of free solvable groups: randomized computations., On the distribution of Atkin and Elkies primes, Evaluation and comparison of two efficient probabilistic primality testing algorithms, On the complexity of inverting integer and polynomial matrices, Iterative refinement for linear systems in variable-precision arithmetic, On the complexity of regular-grammars with integer attributes, Complexity measures for matrix multiplication algorithms, Complexity bounds for the rational Newton-Puiseux algorithm over finite fields, The bit-operation complexity of matrix multiplication and of all pair shortest path problem, Complexity of algorithms and computations, Accelerating Pollard's rho algorithm on finite fields, Single-factor lifting and factorization of polynomials over local fields, New higher-order methods for the simultaneous inclusion of polynomial zeros, Sequential solution to Kepler's equation, Relaxed algorithms for \(p\)-adic numbers, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., Higher Newton polygons and integral bases, Efficient decomposition of separable algebras., Inverting a Vandermonde matrix in minimum parallel time, Relaxed Hensel lifting of triangular sets, The complexity of computing the number of strings of given length in context-free languages, Comments to my works, written by myself, The computational complexity and approximability of a series of geometric covering problems, Discrete convolution with modulo operations, Fast computation of the number of solutions to \(x_1^2 + \cdots + x_k^2 \equiv \lambda \pmod{n}\), On fast multiplication of polynomials over arbitrary algebras, On computational efficiency for multi-precision zero-finding methods, Efficient computation of the characteristic polynomial of a threshold graph, Multiplication, division, and shift instructions in parallel random access machines, Backtracking-assisted multiplication, Solving structured linear systems with large displacement rank, Existence and efficient construction of fast Fourier transforms on supersolvable groups, Minimum-complexity pairing functions, Efficient computation of the characteristic polynomial of a tree and related tasks, Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding, Chunky and equal-spaced polynomial multiplication, Fast modular transforms, On the complexities of multipoint evaluation and interpolation, Controlled non-uniform random generation of decomposable structures, Newton's method and FFT trading, A survey of techniques in applied computational complexity, A low complexity probabilistic test for integer multiplication, Realizing Boolean functions on disjoint sets of variables, Integer programming with 2-variable equations and 1-variable inequalities, Riemann's hypothesis and tests for primality, Computing rank-width exactly, Parallel implementation of multiple-precision arithmetic and 2,576,980,370,000 decimal digits of \(\pi \) calculation, A randomized sublinear time parallel GCD algorithm for the EREW PRAM, Fast multiplication of polynomials over fields of characteristic 2, Optimal routing in double loop networks, The Fast Fourier Transform by polynomial evaluation, Finite approximate approach to the study of the complexity of recursive predicates, Functional decomposition of polynomials: the wild case, Fast arithmetic for triangular sets: from theory to practice, Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)], Fast evaluation of holonomic functions, A cache-friendly truncated FFT, Dynamic programming bi-criteria combinatorial optimization, An exact algorithm for subgraph homeomorphism, Fast conversion algorithms for orthogonal polynomials, Algorithms for exponentiation in finite fields, Computational strategies for the Riemann zeta function, Analysis of algorithms on problems in general abelian groups, FFT-like multiplication of linear differential operators, Multiplication is the easiest nontrivial arithmetic function, Bit complexity of matrix products, Self-testing/correcting with applications to numerical problems, Computing in general Abelian groups is hard, Verifying nonrigidity, Finite field towers: Iterated presentation and complexity of arithmetic., On the complexity of skew arithmetic, A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line, A multimodular algorithm for computing Bernoulli numbers, Tensors in computations, On computation of the Bessel function by summing up the series, Factoring multivariate polynomials via partial differential equations, Fast online multiplication of real numbers, Efficient Computation of the Characteristic Polynomial of a Threshold Graph, The twenty-fourth Fermat number is composite, QUANTUM PHASE ESTIMATION WITH AN ARBITRARY NUMBER OF QUBITS, Computing special powers in finite fields, Some basic information on information-based complexity theory, Polynomial Multiplication over Finite Fields in Time \( O(n \log n \), Squeezing Feasibility, A search for Wilson primes, Generalization of the Ball-Collision Algorithm, Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations, A quasi-linear time algorithm for computing modular polynomials in dimension 2, Fast Computation of Some Special Integrals of Mathematical Physics, Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates, Trans-dichotomous algorithms without multiplication — some upper and lower bounds, Algorithms for Propositional Model Counting, On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms, Efficient Generic Quotients Using Exact Arithmetic, On the computational complexity of compressed power series, Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks, A quantum version of Pollard's Rho of which Shor's algorithm is a particular case, Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity, Phragmén's voting methods and justified representation, Sub-cubic cost algorithms for the all pairs shortest path problem, Fast norm computation in smooth-degree abelian number fields, Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates, Interview with Volker Strehl, Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation, Computation of triangular integral bases, Faster integer multiplication using short lattice vectors, Reduction-free multiplication for finite fields and polynomial rings, Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond, Fast integer multiplication using generalized Fermat primes, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, Full orbit sequences in affine spaces via fractional jumps and pseudorandom number generation, Modular polynomials via isogeny volcanoes, Derivation and Analysis of Fast Bilinear Algorithms for Convolution, AI-Completeness: Using Deep Learning to Eliminate the Human Factor, Local computation of differents and discriminants, \((1+i)\)-ary GCD computation in \(\mathbb Z[i\) as an analogue to the binary GCD algorithm.], Factoring polynomials over finite fields: A survey, Fast algorithms for computing isogenies between elliptic curves, Sylvester-Habicht sequences and fast Cauchy index computation, Discrete Weighted Transforms and Large-Integer Arithmetic, Algebraic complexities and algebraic curves over finite fields, Complexity of OM factorizations of polynomials over local fields, Accelerating the CM method, Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs, Identifying supersingular elliptic curves, On Orders of Optimal Normal Basis Generators, Detecting perfect powers in essentially linear time, A Gröbner free alternative for polynomial system solving, Basic Polynomial Algebra Subprograms, On the Complexity of the Montes Ideal Factorization Algorithm, Congruent Number Theta Coefficients to 1012, Factoring Polynomials over Local Fields II, Information theory and the complexity of boolean functions, Factoring polynomials over local fields., Unnamed Item, Speeding Up the Pollard Rho Method on Prime Fields, Faster integer multiplication using plain vanilla FFT primes, Fast convolutions meet Montgomery, The computational complexity of recognizing permutation functions, A Rigorous Subexponential Algorithm For Computation of Class Groups, A Parallel Algorithm for Multiple-Precision Division by a Single-Precision Integer, Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size, Two efficient algorithms for the computation of ideal sums in quadratic orders, Faster algorithms for the square root and reciprocal of power series, Computing Hilbert class polynomials with the Chinese remainder theorem, Unnamed Item, Lower Bounds for Multiplication via Network Coding, An 𝑂̃(log²(𝑁)) time primality test for generalized Cullen numbers, Irregular primes to 163 million, Code Generation for Polynomial Multiplication, On the Complexity of Reliable Root Approximation, Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work, Binary Addition Chain on EREW PRAM, Accurate and efficient evaluation of Schur and Jack functions, Computing prime divisors in an interval, A primality test for 𝐾𝑝ⁿ+1 numbers, Unnamed Item, Modular exponentiation via the explicit Chinese remainder theorem, Primality Test Via Quantum Factorization, Towards an Implementation of a Computer Algebra System in a Functional Language, On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average, The whole can be very much less than the sum of its parts, Fast Convolutions of Packed Strings and Pattern Matching with Wildcards, Infinite Sets of Primes with Fast Primality Tests and Quick Generation of Large Primes, HIGH PRECISION INTEGER ADDITION, SUBTRACTION AND MULTIPLICATION WITH A GRAPHICS PROCESSING UNIT, HIGH PRECISION INTEGER MULTIPLICATION WITH A GPU USING STRASSEN'S ALGORITHM WITH MULTIPLE FFT SIZES, The basic polynomial algebra subprograms, Hensel lifting and bivariate polynomial factorisation over finite fields, Polynomial factorization over ${\mathbb F}_2$, Computational Complexity of Fourier Transforms Over Finite Fields, Fast evaluation algorithms for elementary algebraic and inverse functions using the FEE method, Fast exact Bayesian inference for sparse signals in the normal sequence model, Complexity results for triangular sets, Computing Frobenius maps and factoring polynomials, Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction, Computing the torsion points of a variety defined by lacunary polynomials, A certified program for the Karatsuba method to multiply polynomials, Efficient data mappings for parity-declustered data layouts, Inapproximability results for equations over finite groups, The delay of circuits whose inputs have specified arrival times, Supercomputer environment for recursive matrix algorithms, On efficiency of notations for natural numbers, ALGORITHMS TO IDENTIFY ABUNDANTp-SINGULAR ELEMENTS IN FINITE CLASSICAL GROUPS, Fast generation of prime numbers and secure public-key cryptographic parameters., Constructing normal bases in finite fields, Polynomial evaluation and interpolation on special sets of points, The shifted number system for fast linear algebra on integer matrices, A fast algorithm for computing the number of magic series, Segment LLL reduction of lattice bases using modular arithmetic, Distant decimals of \(\pi \): formal proofs of some algorithms computing them and guarantees of exact computation, Parameterized and exact algorithms for class domination coloring, Integer multiplication in time \(O(n\log n)\), Optimal and nearly optimal algorithms for approximating polynomial zeros, An algorithm for canonical forms of finite subsets of \(\mathbb {Z}^d\) up to affinities, Efficiently correcting matrix products, On a fast algorithm for computing the Fourier transform, Quantum arithmetic with the quantum Fourier transform, High-Performance Ideal Lattice-Based Cryptography on 8-Bit ATxmega Microcontrollers, Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, Faster FPTASes for counting and random generation of knapsack solutions, Normal bases from 1-dimensional algebraic groups, Strong pseudoprimes to twelve prime bases, Efficient authentication from hard learning problems, A fast algorithm for computing the digamma function, Fast evaluation of the hypergeometric function \(_pF_{p-1}\)(a;b;z) at the singular point \(z = 1\) by means of the Hurwitz zeta function \(\xi(\alpha,s)\)., The equivariant complexity of multiplication in finite field extensions, A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving, Fast structured matrix computations: tensor rank and Cohn-Umans method, Parameterized and Exact Algorithms for Class Domination Coloring, Extensions of dynamic programming for multi-stage combinatorial optimization, Fast skew-feedback shift-register synthesis, On the computation of the HNF of a module over the ring of integers of a number field, Polynomial root finding over local rings and application to error correcting codes, Scientific achievements of Anatolii Alekseevich Karatsuba, Inversion of circulant matrices over $\mathbf{Z}_m$, Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers, Fast computation of special resultants, Efficient accelero-summation of holonomic functions, Efficient decomposition of associative algebras over finite fields, A fast version of the Schur-Cohn algorithm., Fast linear algebra is stable, Faster Polynomial Multiplication via Discrete Fourier Transforms, Fast amortized multi-point evaluation, New algorithms for relaxed multiplication, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, On taking square roots without quadratic nonresidues over finite fields, Change of order for regular chains in positive dimension, Computing the bound of an Ore polynomial. Applications to factorization, On the complexity of computing with planar algebraic curves, From implicit to recursive equations, Elliptic periods and primality proving, An algorithm for multiple-precision floating-point multiplication, Analysis of Rabin's irreducibility test for polynomials over finite fields, Algorithms for propositional model counting, Improved method for finding optimal formulas for bilinear maps in a finite field, Fast algorithm for ``error-free convolution computation using Mersenne--Lucas codes, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, Efficient exact computation of iterated maps, Integer factoring and compositeness witnesses, The complexity of class polynomial computation via floating point approximations, Computing modular polynomials in quasi-linear time, Accurate SVDs of polynomial Vandermonde matrices involving orthonormal polynomials, A framework for deterministic primality proving using elliptic curves with complex multiplication, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, A note on the multiple-recursive matrix method for generating pseudorandom vectors, Multiplication algorithm based on Collatz function, Fast Hermite interpolation and evaluation over finite fields of characteristic two, A primality test for \(4Kp^n-1\) numbers, Smoothness testing of polynomials over finite fields, Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations, Subquadratic-time algorithms for normal bases, Elliptic periods for finite fields, Computing the depth distribution of a set of boxes, Computing Hermite and Smith normal forms of triangular integer matrices, A new algorithm on the minimal rational fraction representation of feedback with carry shift registers, Small one-dimensional Euclidean preference profiles, A method of constructing fast algorithms in the k-valued logic, An in-place truncated Fourier transform, Computing Puiseux series: a fast divide and conquer algorithm, Extracting approximate patterns, Fast on-line integer multiplication, Efficient big integer multiplication and squaring algorithms for cryptographic applications, Functional programming concepts and straight-line programs in computer algebra, Exact real arithmetic using centred intervals and bounded error terms, Amortized multi-point evaluation of multivariate polynomials, Fast enumeration of words generated by Dyck grammars, Taking roots over high extensions of finite fields, Chinese remainder theorem for cyclotomic polynomials in \(\mathbb Z[X\)], Optimization of multidigit multiplication based on discrete (Fourier, cosine, sine) transforms in the parallel computing model, Learning Poisson binomial distributions, Fast computation of the biquadratic residue symbol., Relax, but don't be too lazy
Cites Work
