COMPOSING POWER-SERIES OVER A FINITE RING IN ESSENTIALLY LINEAR-TIME

Authors
BERNSTEIN DJ
Citation
Dj. Bernstein, COMPOSING POWER-SERIES OVER A FINITE RING IN ESSENTIALLY LINEAR-TIME, Journal of symbolic computation, 26(3), 1998, pp. 339-341
Citations number
5
Categorie Soggetti
Mathematics,"Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods
Journal title
Journal of symbolic computation → ACNP
ISSN journal
07477171
Volume
26
Issue
3
Year of publication
1998
Pages
339 - 341
Database
ISI
SICI code
0747-7171(1998)26:3<339:CPOAFR>2.0.ZU;2-B
Abstract
Fix a finite commutative ring R. Let u and v be power series over R, w ith v(0) = 0. This paper presents an algorithm that computes the first n terms of the composition u(v), given the first n terms of u and v, in n(1+0(1)) ring operations. The algorithm is very fast in practice w hen R has small characteristic. (C) 1998 Academic Press.