Faster relaxed multiplication
type: Dataset
description: In previous work, we have introduced several fast algorithms for relaxed power series multiplication (also known under the name on-line multiplication) up till a given order n. The fastest currently known algorithm works over an effective base field K with sufficiently many 2^p-th roots of unity and has algebraic time complexity O(n log n exp (2 sqrt (log 2 log log n))). In this note, we will generalize this algorithm to the cases when K is replaced by an effective ring of positive characteristic or by an effective ring of characteristic zero, which is also torsion-free as a Z-module and comes with an additional algorithm for partial division by integers. We will also present an asymptotically faster algorithm for relaxed multiplication of p-adic numbers.
issued: 2026-05-05T12:35:08.150665
language: en
modified: 2026-05-05T12:35:08.150670
contact point: Organization
  fn: CCSD
keyword: computer-algebra
keyword: fft
keyword: infoeu-reposemanticspreprint
keyword: infoinfo-mscomputer-science-csmathematical-software-csms
keyword: msc-68w30-30b10-68w25-33f05-11y55-42-04
keyword: multiplication
keyword: on-line-algorithm
keyword: power-series
keyword: preprints-working-papers-
landing page: https://hal.science/hal-00687479

Faster relaxed multiplication
type: Distribution
format: HTML
issued: 2026-05-05T12:35:08.152650
modified: 2026-05-05T12:35:08.140635
access URL: https://hal.science/hal-00687479

test_moissonnage_selune
type: Agent