You can't find information on the fastest way to calculate because it is one of the quickest operations that can be done on a computer. Using integer division (i.e. $\frac a b = \lfloor \frac a b \rfloor$), the modulo operation is just $r = a - (\frac a b) b$. In practice this can be done in tens of computer clock cycles, which is almost instantaneous. In general, whenever library functions are available for some function you should use those over anything you can write on your own; they are often the fastest known algorithms and optimized by the compiler. As mentioned in a comment above, most languages contain a modulo operation by default.
Modular Exponentiation is the general term for $a^b\pmod c$. As an example, consider something "easy" like $2^{1386}\pmod{1387}$. Rewriting $1386$ as a sum of its binary digits helps later in this process, so note that $1386=2^{10}+2^8+2^6+2^5+2^3+2^1$.
So then we have
$$2^{1386}=2^{2^{10}+2^8+2^6+2^5+2^3+2^1}=2^{2^{10}}\cdot 2^{2^8}\cdot 2^{2^6}\cdot 2^{2^5}\cdot 2^{2^3}\cdot 2^{2^1}$$
I have written out the calculations for the above values, so rather than redoing that, here is what they become:
$$2^{2^1}=4,\ 2^{2^3}=256,\ 2^{2^5}\equiv -260\pmod{1387}\\2^{2^6}\equiv 1024\pmod {1387},\ 2^{2^8}\equiv 16\pmod{1387},\\2^{2^{10}}\equiv 347\pmod{1387}$$
Now we have a series of small numbers to multiply together, which is much faster than doing a loop $1386$ times and multiplying by $2$ each time and taking the modulus.
So the question becomes, why did we rewrite our exponent as a sum of binary digits? Essentially, it is because taking the square of a number multiplies its exponent by $2$:
$$(2^2)^2=2^{2^2}\\(2^{2^2})^2=2^{2^3}\\(2^{2^3})^2=2^{2^4}\\\dots$$
and in general,
$$(a^b)^2=a^{2b}\\(a^{2^b})^2=a^{2^{b+1}}$$
So the algorithm used by the ppow
function is implementing this process; it squares the current result and applies the modulus, asks a recursive version of itself for the result with half the current exponent, and asks for the current value as well if the current exponent is odd, thereby capturing each binary digit of the exponent. Finding the value modulo $1387$ of the numbers $2^{2^{10}},\ 2^{2^8},\ 2^{2^6},\ 2^{2^5},\ 2^{2^3},\ 2^{2^1}$ was faster than looping $1386$ times because we only needed to square $2$ ten times to get to the value of $2^{2^{10}}$, and we got the modular value of all six numbers along the way.
This algorithm could be rewritten to use any particular numeric base in the exponent, but then that numeric base would also need to be the common exponent. So instead of squaring each time, we could cube each time and consider the exponent in base $3$, and so on.
Best Answer
We consider the Fibonacci sequence with $f_0=0,f_1=1$ and $f_{n+2}=f_{n+1}+f_n\;\forall\;n\geq0$. Consider the pairs of consecutive Fibonacci numbers $(f_k,f_{k+1})$ modulo $n$. There are only $n^2$ possible pairs like this. Hence by pigeon hole principle $\exists$ two distinct pairs $(f_r,f_{r+1})$ and $(f_s,f_{s+1})$ which are identical modulo $n$. Let $r>s$. Then $$f_r\equiv f_s\pmod{n}$$ $$f_{r+1}\equiv f_{s+1}\pmod{n}$$ which implies $$f_{r+2}=f_r+f_{r+1}\equiv f_s+f_{s+1}=f_{s+2}\pmod{n}$$ and $$f_{r-1}=f_{r+1}-f_r\equiv f_{s+1}-f_s=f_{s-1}\pmod{n}$$ proceeding this way we get that $$f_{r-s}\equiv f_0\pmod{n}, f_{r-s+1}\equiv f_1\pmod{n}$$ hence the sequence $f_n$ is periodic with period $r-s$.
Moreover let $$\mathcal{F}=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}$$ in $GL_2(\mathbb{Z/n\mathbb{Z}})$
If $\pi(n)$ is the Pisano period modulo $n$ then $$\mathcal{F}^{\pi(n)}=I$$
From this we can conclude that the Pisano period is even. $$\mathrm{det}(\mathcal{F}^{\pi(n)})=(-1)^{\pi(n)}=1$$ which implies $\pi(n)$ is even.