I want to know is it possible to calculate $\log({x+1}) \bmod 2^N$ faster than $O(N\sqrt{N}\log{N})$.
I'm only interested in the case that $x$ is integer and $x \bmod 4 = 0$.
1.Naive calculation $O(N^2\log{N})$
First of all, let's estimate the time complexity of naive calculation. By Taylor expansion, $\log({x+1}) = \sum_{i=1}^\infty \frac{1}{i}(-1)^{i+1}x^i$. The number of trainling zeros of $i$ is at most $\log_2(i)$. On the other hand, the number of trailing zeros (in 2-adic) of $x^i$ is $2i$ if $x \bmod 4=0$ and $x \bmod 8\neq 0$. So, if we calculate naively, we need to calculate up to around $N$ th term because higher order terms will become $0$ after taking mod $2^N$. Since the time complexity of multiplication of 2 n-bit integers is $O(n\log n)$, the time complexity of calculating $\log (x+1) \bmod 2^N$ is $O(\sum_{i=1}^{N} N\log{N})=O(N^2\log{N})$.
2. faster calculation $O(N\sqrt{N}\log{N})$
Now, there is an idea to speed up this calculation (I've heard this from maspy_stars-san). Using some integer $M, M'$, the relationship,$(1+2^nM)^2 \bmod 2^N=1+2^{n+1}M' \bmod 2^N$ holds from binomial theorem. Applying this relationship, we get following relationship. \begin{align} \log(x+1)&=\frac{\log\left((x+1)^{2^k}\right)}{2^k} \\ &=\frac{\log(1+2^{k+2}M'')}{2^k} \end{align} In this case, the number of trailing zeros of $i$ th term of $\log(1+x)$ s.t. $x=2^{k+2}M''$ is around $(k+2)i-\log_2i\approx (k+2)i$. So, we need to calculate up to $\frac{N+k}{k+2}$th term. Time complexity of $\log(x+1)$ in this case is $O\left(\sum_{i=1}^{\frac{N+k}{k+2}} (N+k) \log ({N+k})\right)=O\left(\frac{(N+k)^2}{k+2} \log (N+k)\right)$. On the other hand, time complexity of calculating $(x+1)^{2^k} \bmod 2^{N+k}$ is $O\left(k(N+k)\log(N+k)\right)$ by repetated squaring. By putting $k=N^\alpha$, $O\left(\frac{(N+k)^2}{k+2}\right)=O(N^{2-\alpha}+N+N^\alpha)$ and $O(k(N+k))=O(N^{\alpha+1}+N^{2\alpha})$. So, the optimal value of $k$ is $k=\sqrt{N}$ to reduce the time complexity. Now the total time complexity is $O(N\sqrt{N}\log{N})$.
3. My question
Is it possible to calculate $\log({x+1}) \bmod 2^N$ s.t. $x \bmod 4=0$ faster than $O(N\sqrt{N}\log{N})$?