Niech x, y będą dowolnymi liczbami całkowitymi, a, b dowolnymi liczbami całkowitymi różnymi od zera, m – liczbą całkowitą większą niż 1.
Załóżmy, że dany jest ciąg liczb całkowitych zdefiniowany rekurencyjnie:
G₀ = x, G₁ = y
G_n = aG_n-2 + bG_n-1, gdzie n ≥ 2.

Interesuje nas obliczenie G_n mod m dla ustalonej liczby n.
Przyjmując np. x = y = a = b = 1, m = 10 jako G_n mod m dostaniemy ostatnią cyfrę n – tej liczby Fibonacciego.

Algorytm polegający na wyznaczaniu kolejnych wyrazów G_k mod m dla k = 2, 3, ..., n ma złożoność O(n) i dla bardzo dużych wartości n jest niepraktyczny. Można to zrobić o wiele szybciej w czasie O(log n) wykorzystując działania na macierzach oraz szybkie potęgowanie modularne.
Korzystając z indukcji matematycznej łatwo udowodnić następującą tożsamość:

Ze wzoru tego wynika, że należy najpierw obliczyć:

Potęgowanie macierzy odbywa się podobnie jak potęgowanie liczby opisane w artykule szybkie potęgowanie modularne. Jeżeli liczby a i/lub b są niemniejsze niż m to najpierw w macierzy, którą będziemy potęgować zastępujemy te liczby ich resztami z dzielenia przez m. Wprowadzamy macierz pomocniczą X o dwóch wierszach i dwóch kolumnach, która na początku będzie równa macierzy jednostkowej. Dalej, wyznaczamy kolejne cyfry rozwinięcia dwójkowego liczby n – 2. W każdym kroku (których ilość jest równa liczbie cyfr dwójkowych liczby n – 2), przemnażamy macierz X przez samą siebie a wynik mnożenia ponownie przypisujemy pod macierz X. Dodatkowo, jeżeli kolejna cyfra dwójkowa liczby n – 2 (licząc od cyfry najwyższego rzędu) jest równa 1, macierz:
przemnażamy przez macierz X
Na koniec każdy z czterech elementów macierzy X zastępujemy jego resztą z dzielenia przez m.

Ponieważ cyfry dwójkowe liczby n – 2 pobierane są od cyfry najwyższego rzędu, zatem najprościej potęgowanie macierzy modulo m zrealizować rekursywnie tak, jak zostało to wykonane w dołączonej implementacji algorytmu.

Ostatecznie przyjmując:

Otrzymujemy:


Dowod poprawności algorytmu (Adam Mika):