Is there any efficient way of calculating the n-th fibonacci number modulo another number?
Here are two suggestions:

The linear algebra approach. It is known that
$$\begin{bmatrix} 1 &amp; 1 \\ 1 &amp; 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} &amp; F_n \\ F_n &amp;F_{n-1} \end{bmatrix}. $$
You can compute the matrix power using repeated squaring, doing all the calculations modulo your modulus.

Closed form. If your modulus is odd and 5 is a quadratic residue (i.e., 5 has a modular square root) then you can use the explicit formula
$$
F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}.
$$
You can then use Carmichael's function to reduce $n$, and then repeated squaring. Care must be taken when the modulus isn't a prime power.

It is possible that a similar approach works more generally.