2007 · 34 citations · 26 references
ComputingComputer ScienceMathematicsAlgebraAlgorithmsSet TheoryAlgorithm AnalysisComputational AlgebraComputational ComplexityEuclidean AlgorithmNumber-theoretic AlgorithmsRecursion TheoryAxiom SystemsComputational Gcd AlgorithmsDivision AlgorithmsEuclidean DivisionLinear ComplexityModular Arithmetic AlgorithmsMultiplication Algorithms For Large IntegersQuasi-linear Theory
We study arithmetic operations for triangular families of polynomials, concentrating on multiplication in dimension zero. By a suitable extension of fast univariate Euclidean division, we obtain theoretical and practical improvements over a direct recursive approach; for a family of special cases, we reach quasi-linear complexity. The main outcome we have in mind is the acceleration of higher-level algorithms, by interfacing our low-level implementation with languages such as AXIOM or Maple We show the potential for huge speed-ups, by comparing two AXIOM implementations of van Hoeij and Monagan's modular GCD algorithm.
26
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
The Magma Algebra System I: The User Language
Wieb Bosma, John Cannon, Catherine Playoust · Journal of Symbolic Computation · 1997 · 7.4K citations
1990 · 3.1K citations
Modular multiplication without trial division
Peter L. Montgomery · Mathematics of Computation · 1985 · 2.4K citations
Choice Reviews Online · 2000 · 1.6K citations