Homotopy techniques for multiplication modulo triangular sets

DOI10.1016/j.jsc.2011.08.015zbMath1239.68079OpenAlexW2153131327MaRDI QIDQ651881

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

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) Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Related Items (5)

Modular composition modulo triangular sets and applications ⋮ Efficient arithmetic in successive algebraic extension fields using symmetries ⋮ Relaxed Hensel lifting of triangular sets ⋮ Computing in degree \(2^k\)-extensions of finite fields of odd characteristic ⋮ Accelerated tower arithmetic

Uses Software

• Magma
• NTL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Newton's method and FFT trading
• A simple and fast algorithm for computing exponentials of power series
• On fast multiplication of polynomials over arbitrary algebras
• Simple multivariate polynomial multiplication
• The Magma algebra system. I: The user language
• Computation of the decomposition group of a triangular ideal
• Fast computation of special resultants
• The p-adic valuation of k-central binomial coefficients
• Evaluating Polynomials at Fixed Sets of Points
• The truncated fourier transform and applications
• Calcul de résolvantes avec les modules de Cauchy
• Lifting techniques for triangular decompositions
• Multivariate power series multiplication
• Advances in Cryptology - EUROCRYPT 2004
• EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS
• On computer-assisted classification of coupled integrable equations
• Algorithmic Number Theory
• Algorithms in invariant theory
• Using Galois ideals for computing relative resolvents

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