Composing power series over a finite ring in essentially linear time

D.J. Bernstein

    Research output: Contribution to journalArticleAcademicpeer-review

    13 Citations (Scopus)

    Abstract

    Fix a finite commutative ringR. Letuandvbe power series overR, withv(0) = 0. This paper presents an algorithm that computes the firstnterms of the compositionu(v), given the firstnterms ofuandv, inn1 + o(1)ring operations. The algorithm is very fast in practice whenRhas small characteristic.
    Original languageEnglish
    Pages (from-to)339-341
    Number of pages3
    JournalJournal of Symbolic Computation
    Volume26
    Issue number3
    DOIs
    Publication statusPublished - 1998

    Fingerprint

    Dive into the research topics of 'Composing power series over a finite ring in essentially linear time'. Together they form a unique fingerprint.

    Cite this