Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want to calculate X % M (the remainder when X is divided by M).
My approach is to calculate Y % M where Y = 1, 11, 111, ...until reached the number with sqrt(N) times 1, and the algorithm is O(sqrt(N)). I wonder whether there is a O(log(N)) algorithm? N is at the level of 10^16, and M is at the level of 10^9 in this problem.
Yes, there is.
Since $X=\frac{10^N-1}{9}$ and we can find the inverse of $9$ in $(\mathbb{Z}/M\mathbb{Z})^*$ in $O(\log M)$ time with the extended Euclidean algorthm, we just need to find $10^N\pmod{M}$. This can be done in $O(\log N)$ time with the repeated squaring algorithm.
If you know the factorization of $M$ or a large portion of primes dividing $M$, you can even improve the constants with a careful use of the Chinese remainder theorem and the Fermat's little theorem.
For example, assume that we want to find $\frac{10^{100}-1}{9}\pmod{222}$.
Since $222=2\cdot 3\cdot 37$, we only need to find: $$10^{100}\pmod{2},\quad 10^{100}\pmod{27},\quad 10^{100}\pmod{37}.$$ Since $\varphi(27)=18$ and $\varphi(37)=36$, $$10^{100}\equiv 10^{10} \equiv ((10^2)^2\cdot 10)^2\equiv 10\pmod{27},$$ $$10^{100}\equiv 10^{28} \equiv 10\pmod{37}$$ (as it is natural since $27\cdot 37=999|(10^3-1)$), hence: $$\frac{10^{100}-1}{9}\equiv 1\pmod{2},$$ $$\frac{10^{100}-1}{9}\equiv 1\pmod{3},$$ $$\frac{10^{100}-1}{9}\equiv 1\pmod{37},$$ and, putting this relations back together: $$\frac{10^{100}-1}{9}\equiv 1\pmod{222}.$$