### 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$.

**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

**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

**2019-05-10**

1905.04187 | cs.SC

The coefficient sequences of multivariate rational functions appear in many
areas of combinatorics. … show more

**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

**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

**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

**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

**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

**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

**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

**2018-12-31**

1812.11789 | cs.SC

In an earlier article together with Carlos D'Andrea [BDKSV2017], we described
explicit expressions f… show more

**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

**2018-11-05**

1811.01490 | cs.SC

Fast algorithms for integer and polynomial multiplication play an important
role in scientific compu… show more

**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

**2018-11-21**

1811.08616 | cs.SC

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

**2014-04-17**

1404.5525 | cs.NA

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