Residue class of a huge repunit modulus a huge number 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.
 A: 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}.$$
