Re: p-adic logarithm

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Jun 25, 2016 at 03:33:48PM +0100, Kevin Buzzard wrote:
> I think that one efficient way to compute Iwasawa's p-adic log (i.e.
> normalised so that log(p)=0) is to take your random element x of your
> random p-adic field, raise it to some power n until its valuation is
> an integer multiple of the valuation of p, divide by an appropriate
> power of p to get a unit u=x^n/p^m, raise the unit to an appropriate
> power (e.g. q-1) until it's a 1-unit, raise this 1-unit to an
> appropriate power (a power of p) until it's congruent to 1 modulo a
> sufficiently large power of p for the power series for log to
> converge, and then plug it into the power series. Once we've computed
> ell:=log(x^N/p^M) we just divide by N to get log(x).

Yes, it is how ZpXQ_log works, except it uses the series for atanh which
converges faster and uses Brent and Kung algorithm to evaluate the
series, which leads to an algorithm using O(n^(1/3)) multiplication and
O(n^(2/3)) additions which is better in practice than O(n^(1/2))
multiplications and O(n^(1/2)) additions.

Cheers,
Bill