On fast multiplication of polynomials over arbitrary algebras

From MaRDI portal

Publication:1186518

Jump to:navigation, search

DOI10.1007/BF01178683zbMath0766.68055MaRDI QIDQ1186518

David G. Cantor, Erich L. Kaltofen

Publication date: 28 June 1992

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

polynomial multiplication procedure Schönhage-Strassen algorithm

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Parallel algorithms in computer science (68W10) Polynomials, factorization in commutative rings (13P05)

Related Items

Polynomial Multiplication over Finite Fields in Time \( O(n \log n \), Skew-polynomial-sparse matrix multiplication, Beating binary powering for polynomial matrices, Rinocchio: SNARKs for ring arithmetic, Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology, High-order lifting for polynomial Sylvester matrices, A fast randomized geometric algorithm for computing Riemann-Roch spaces, Factoring polynomials over finite fields: A survey, On Orders of Optimal Normal Basis Generators, Asymptotically fast polynomial matrix algorithms for multivariable systems, On the Complexity of the Montes Ideal Factorization Algorithm, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, The computational complexity of recognizing permutation functions, Unnamed Item, Unnamed Item, Polynomial-division-based algorithms for computing linear recurrence relations, Algebraic improvements of numerical algorithms: Interpolation and economization of Taylor series, Computing Frobenius maps and factoring polynomials, Factoring multivariate polynomials via partial differential equations, Computing minimal interpolation bases, Deterministic root finding over finite fields using Graeffe transforms, On the complexity of integer matrix multiplication, Faster sparse multivariate polynomial interpolation of straight-line programs, An isomorphism test for modules over a non-commutative PID. Applications to similarity of Ore polynomials., On design of circuits of logarithmic depth for inversion in finite fields, Polynomial evaluation and interpolation on special sets of points, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Computing Zeta Functions of Artin–schreier Curves over Finite Fields, Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields, On the complexity exponent of polynomial system solving, Hardness results and spectral techniques for combinatorial problems on circulant graphs, Efficient information-theoretic secure multiparty computation over \(\mathbb{Z}/p^k\mathbb{Z}\) via Galois rings, Complexity of computation in finite fields, Efficiently correcting matrix products, Univariate polynomial factorization over finite fields, Factoring polynomials of the form \(f(x^n) \in \mathbb{F}_q [x\)], Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, Normal bases from 1-dimensional algebraic groups, Fast systematic encoding of multiplicity codes, Directed evaluation, Multi-point evaluation in higher dimensions, On the evaluation of some sparse polynomials, Algorithms for simultaneous Hermite-Padé approximations, Complexity bounds for the rational Newton-Puiseux algorithm over finite fields, An algebraic attack on ciphers with low-degree round functions: application to full MiMC, The equivariant complexity of multiplication in finite field extensions, Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation, An improved method for predicting truncated multiple recursive generators with unknown parameters, Computing isomorphisms and embeddings of finite fields, Relaxed algorithms for \(p\)-adic numbers, Polynomial root finding over local rings and application to error correcting codes, Detecting lacunary perfect powers and computing their roots, Homotopy techniques for multiplication modulo triangular sets, New techniques for the computation of linear recurrence coefficients, Smoothness and factoring polynomials over finite fields, Relaxed Hensel lifting of triangular sets, Fast computation of special resultants, Superfast algorithms for Cauchy-like matrix computations and extensions, Faster Polynomial Multiplication via Discrete Fourier Transforms, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Fast amortized multi-point evaluation, Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation, Efficient computation of the characteristic polynomial of a threshold graph, New algorithms for relaxed multiplication, Solving structured linear systems with large displacement rank, Verification protocols with sub-linear communication for polynomial matrix operations, Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields, Change of order for regular chains in positive dimension, On the complexity of the Lickteig-Roy subresultant algorithm, Computing the bound of an Ore polynomial. Applications to factorization, Factoring Polynomials over Finite Fields Using Differential Equations and Normal Bases, Fast algorithms for computing isogenies between elliptic curves, From implicit to recursive equations, An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation, Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Chunky and equal-spaced polynomial multiplication, Essentially optimal computation of the inverse of generic polynomial matrices, Subquadratic-time factoring of polynomials over finite fields, Efficient parallel factorization and solution of structured and unstructured linear systems, Computing in degree \(2^k\)-extensions of finite fields of odd characteristic, Analysis of Rabin's irreducibility test for polynomials over finite fields, On the complexities of multipoint evaluation and interpolation, Newton's method and FFT trading, Improved method for finding optimal formulas for bilinear maps in a finite field, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, Faster integer multiplication using plain vanilla FFT primes, Modular composition via factorization, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, A note on the multiple-recursive matrix method for generating pseudorandom vectors, Fast multivariate multi-point evaluation revisited, Fast computation of approximant bases in canonical form, Fast Hermite interpolation and evaluation over finite fields of characteristic two, Elliptic periods for finite fields, MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING, Functional decomposition of polynomials: the tame case, Fast arithmetic for triangular sets: from theory to practice, Code Generation for Polynomial Multiplication, An in-place truncated Fourier transform, Guessing Gröbner bases of structured ideals of relations of sequences, Interpolation of polynomials given by straight-line programs, Algorithms and complexity for Turaev-Viro invariants, Computing Puiseux series: a fast divide and conquer algorithm, Fast conversion algorithms for orthogonal polynomials, Algorithms for exponentiation in finite fields, Accelerated tower arithmetic, Amortized multi-point evaluation of multivariate polynomials, Taking roots over high extensions of finite fields, Polynomial modular product verification and its implications, Arithmetic complexity of certain linear transformations, Relax, but don't be too lazy, Hensel lifting and bivariate polynomial factorisation over finite fields, Polynomial factorization over ${\mathbb F}_2$, On the complexity of skew arithmetic, The arithmetic computational complexity of linear transforms, On the effect of projection on rank attacks in multivariate cryptography

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1186518&oldid=12054292"