As I see it, $p$-adic integers work very similar to formal power series over $x$ (e g. with regards to Hensel lifting).
When it comes to computing $\log P(x)$, one may use the formula
$$
(\log P)' = \frac{P'}{P}
$$
to compute the expansion of the logarithm of $P(x)$ with $P(0)=1$ as
$$
\log P \equiv \int \frac{P'}{P} dx \pmod{x^n}.
$$
This is the main trick to compute first $n$ coefficients of $\log P(x)$ in $O(M(n))$, where $M(n)$ is the maximum time needed to compute the product of two polynomials of degree at most $n$.
Is there any similar way to compute modulo $p^n$ the expansion of the $p$-adic logarithm of the $p$-adic integer $r$ such that $r \equiv 1 \pmod p$ in $O(M(n))$?
As I see it, the regular notion of polynomial derivatives can't be applied directly to $p$-adic integers, as $(uv)' = u'v+uv'$ woudln't hold. So, maybe there is a way to define some other reasonably invertible function $d(r)$ which is simple enough to compute and such that
$$
d(uv) = u d(v) + v d(u)
$$
for any $p$-adic numbers $u$ and $v$?
Best Answer
There is a method with bit complexity $O(n \log^3 n)$, which is an adaptation of the "bit-burst algorithm" for real and complex functions. The idea here is to integrate the solution of a differential equation using binary splitting evaluation of power series, using integration steps that converge exponentially to the evaluation point (in steps of $2^{-2^n}$ in the real setting, and $p$-adically in steps of $p^{2^n}$).
This generalizes to many functions satisfying simple differential equations. In that sense, it is related to the integration method for formal power series, though not exactly the same. The technique is discussed in significant detail in the recent (2021) preprint "Fast evaluation of some p-adic transcendental functions" by Xavier Caruso, Marc Mezzarobba, Nobuki Takayama, and Tristan Vaccon (https://hal.archives-ouvertes.fr/hal-03263044v1).
I don't know who came up with this method in the $p$-adic setting originally, and the authors of the above paper describe it as "folklore". David Harvey certainly knew about it in 2007 (remark after Proposition 9 in https://arxiv.org/abs/0708.3404), and I learned about it talking to David in 2012. Sebastian Pancratz and I then implemented asymptotically fast $p$-adic exponentials and logarithms in FLINT, confirming that the method works very well in practice.