✦ LIBER ✦
Composing Power Series Over a Finite Ring in Essentially Linear Time
✍ Scribed by Daniel J. Bernstein
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 261 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0747-7171
No coin nor oath required. For personal study only.
✦ Synopsis
Fix a finite commutative ring R. Let u and v be power series over R, with 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+o(1) ring operations. The algorithm is very fast in practice when R has small characteristic.