ML p(r)ior | Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field

### Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field

2016-02-01
1602.00545 | cs.SC
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 $N$th coefficient of an algebraic series uses differential equations and has arithmetic complexity quasi-linear in $\sqrt{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$.

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

# Related Articles

2019-03-08
1903.03278 | cs.SC

It is well known that for any finite Galois extension field $K/F$, with Galois group $G = \mathrm{Ga… show more Highlights - Most important sentences from the article 2019-05-12 1905.04614 | cs.SC Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear… show more Highlights - Most important sentences from the article 2019-05-10 1905.04187 | cs.SC The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. … show more Highlights - Most important sentences from the article 2018-02-23 1802.08653 | math.NT In 1994, Becker conjectured that if$F(z)$is a$k$-regular power series, then there exists a$k$-re… show more Highlights - Most important sentences from the article 2019-04-26 1904.11705 | cs.SC Let$S\subset R^n$be a compact basic semi-algebraic set defined as the real solution set of multiva… show more Highlights - Most important sentences from the article 2018-11-25 1811.10062 | cs.SC We consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of… show more Highlights - Most important sentences from the article 2018-10-25 1810.11068 | math.NT We present a probabilistic Las Vegas algorithm for computing the local zeta function of a genus-$g$… show more Highlights - Most important sentences from the article 2017-12-02 1712.00669 | cs.CG We present a novel randomized algorithm to factor polynomials over a finite field$\F_q$of odd char… show more Highlights - Most important sentences from the article 2018-06-15 1806.05834 | math.NT We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-3 hyperellipt… show more Highlights - Most important sentences from the article 2018-07-22 1807.08289 | cs.SC Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objec… show more Highlights - Most important sentences from the article 2018-12-31 1812.11789 | cs.SC In an earlier article together with Carlos D'Andrea [BDKSV2017], we described explicit expressions f… show more Highlights - Most important sentences from the article 2018-12-17 1812.06828 | cs.CC The existence of string functions, which are not polynomial time computable, but whose graph is chec… show more Highlights - Most important sentences from the article 2018-11-05 1811.01490 | cs.SC Fast algorithms for integer and polynomial multiplication play an important role in scientific compu… show more Highlights - Most important sentences from the article 2017-12-12 1712.04177 | cs.SC Consider a zero-dimensional ideal$I$in$\mathbb{K}[X_1,\dots,X_n]\$. Inspired by Faug\`ere and Mou'… show more

Highlights - Most important sentences from the article

2018-11-21
1811.08616 | cs.SC

A lot of information concerning solutions of linear differential equations can be computed directly … show more

Highlights - Most important sentences from the article

2014-04-17
1404.5525 | cs.NA

In this paper, we study iterative methods on the coefficients of the rational univariate representat… show more

Highlights - Most important sentences from the article