Homotopy techniques for multiplication modulo triangular sets

DOI10.1016/J.JSC.2011.08.015MaRDI QIDQ651881zbMATH OpenOpenAlexFDO

Authors Alin Bostan, Muhammad F. I. Chowdhury, Joris van der Hoeven, Éric Schost

Publication date 19 December 2011

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-00819155/file/BoChHoSc11.pdf

zbMATH Keywords

interpolationdeformationmultiplicationHensel lemmaquasi-linear complexitytriangular sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Recommendations

• Fast arithmetic for triangular sets: from theory to practice
• Fast arithmetic for triangular sets: from theory to practice
• Modular composition modulo triangular sets and applications
• On the complexity of computing with zero-dimensional triangular sets
• Multivariate power series multiplication

Cites work

• scientific article; zbMATH DE number 4128945 (Why is no real title available?)
• scientific article; zbMATH DE number 16654 (Why is no real title available?)
• scientific article; zbMATH DE number 3533996 (Why is no real title available?)
• scientific article; zbMATH DE number 1253989 (Why is no real title available?)
• scientific article; zbMATH DE number 2151224 (Why is no real title available?)
• scientific article; zbMATH DE number 2151230 (Why is no real title available?)
• A simple and fast algorithm for computing exponentials of power series
• Advances in Cryptology - EUROCRYPT 2004
• Algorithmic Number Theory
• Algorithms in invariant theory
• Calcul de résolvantes avec les modules de Cauchy
• Computation of the decomposition group of a triangular ideal
• EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS
• Evaluating Polynomials at Fixed Sets of Points
• Fast arithmetic for triangular sets: from theory to practice
• Fast computation of special resultants
• Faster integer multiplication
• Lifting techniques for triangular decompositions
• Modern computer algebra
• Multivariate power series multiplication
• Newton's method and FFT trading
• On computer-assisted classification of coupled integrable equations
• On fast multiplication of polynomials over arbitrary algebras
• On the complexity of the D5 principle
• Simple multivariate polynomial multiplication
• The Magma algebra system. I: The user language
• The \(p\)-adic valuation of \(k\)-central binomial coefficients
• The truncated fourier transform and applications
• Using Galois ideals for computing relative resolvents

Cited in

(8)

• Accelerated tower arithmetic
• On the complexity of the D5 principle
• Modular composition modulo triangular sets and applications
• Fast arithmetic for triangular sets: from theory to practice
• Computing in degree \(2^k\)-extensions of finite fields of odd characteristic
• Relaxed Hensel lifting of triangular sets
• Efficient arithmetic in successive algebraic extension fields using symmetries
• Fast arithmetic for triangular sets: from theory to practice

Describes a project that uses

Uses Software

• NTL
• Magma

This page was built for publication: Homotopy techniques for multiplication modulo triangular sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q651881)