@inproceedings{10.1145/2930889.2930904,
    Abstract = {We address the question of computing one selected term of an algebraic power series. In characteristic zero, the best algorithm currently known for computing the\textasciitilde Nth coefficient of an algebraic series uses differential equations and has arithmetic complexity quasi-linear in √N. We show that over a prime field of positive characteristic p, the complexity can be lowered to O(log N). The mathematical basis for this dramatic improvement is a classical theorem stating that a formal power series with coefficients in a finite field is algebraic if and only if the sequence of its coefficients can be generated by an automaton. We revisit and enhance two constructive proofs of this result for finite prime fields. The first proof uses Mahler equations, whose sizes appear to be prohibitively large. The second proof relies on diagonals of rational functions; we turn it into an efficient algorithm, of complexity linear in log N and quasi-linear in p.},
    Address = {New York, NY, USA},
    Author = {Bostan, Alin and Christol, Gilles and Dumas, Philippe},
    BookTitle = {Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation},
    File = {Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field - SlidesDumas.pdf},
    ISBN = {9781450343800},
    Keywords = {diagonals, finite fields, algebraic series, section operators, algebraic complexity, mahler equations, p-rational series},
    Location = {Waterloo, ON, Canada},
    Pages = {119--126},
    Publisher = {Association for Computing Machinery},
    Series = {ISSAC '16},
    Title = {Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field},
    URL = {https://doi.org/10.1145/2930889.2930904},
    Year = {2016},
    bdsk-url-1 = {https://doi.org/10.1145/2930889.2930904},
    date-added = {2021-11-25 12:12:24 +0100},
    date-modified = {2021-11-25 12:12:24 +0100},
    file-2 = {Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field - BoChDu16.pdf},
    numpages = {8},
    doi = {10.1145/2930889.2930904}
}

@inproceedings{10.1145/2930889.2930904, Abstract = {We address the question of computing one selected term of an algebraic power series. In characteristic zero, the best algorithm currently known for computing the\textasciitilde Nth coefficient of an algebraic series uses differential equations and has arithmetic complexity quasi-linear in √N. We show that over a prime field of positive characteristic p, the complexity can be lowered to O(log N). The mathematical basis for this dramatic improvement is a classical theorem stating that a formal power series with coefficients in a finite field is algebraic if and only if the sequence of its coefficients can be generated by an automaton. We revisit and enhance two constructive proofs of this result for finite prime fields. The first proof uses Mahler equations, whose sizes appear to be prohibitively large. The second proof relies on diagonals of rational functions; we turn it into an efficient algorithm, of complexity linear in log N and quasi-linear in p.}, Address = {New York, NY, USA}, Author = {Bostan, Alin and Christol, Gilles and Dumas, Philippe}, BookTitle = {Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation}, File = {Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field - SlidesDumas.pdf}, ISBN = {9781450343800}, Keywords = {diagonals, finite fields, algebraic series, section operators, algebraic complexity, mahler equations, p-rational series}, Location = {Waterloo, ON, Canada}, Pages = {119--126}, Publisher = {Association for Computing Machinery}, Series = {ISSAC '16}, Title = {Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field}, URL = {https://doi.org/10.1145/2930889.2930904}, Year = {2016}, bdsk-url-1 = {https://doi.org/10.1145/2930889.2930904}, date-added = {2021-11-25 12:12:24 +0100}, date-modified = {2021-11-25 12:12:24 +0100}, file-2 = {Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field - BoChDu16.pdf}, numpages = {8}, doi = {10.1145/2930889.2930904} }