Bill Allombert on Sat, 25 Jun 2016 22:57:58 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: p-adic logarithm |
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