Liczby pierwsze

Liczba pierwsza to taka liczba, która ma dokładnie dwa dzielniki. Wydawać by się mogło, że taka cecha nie jest bardzo interesująca, w każdym razie nie bardziej niż posiadanie trzech czy czterech dzielników. Jednak własność posiadania akurat dwóch dzielników jest bardzo ważna i na tyle często używana w matematyce, że zyskała osobną nazwę.¹ Mimo dużego zainteresowania liczbami pierwszymi wśród matematyków, nieznany jest szybki algorytm, który z całą pewnością jest w stanie stwierdzić, czy liczba jest pierwsza. Z drugiej strony jeden z najpopularniejszych algorytmów szyfrujących, RSA, wykorzystywany m.in. w bankowości, właśnie korzysta z dużych liczb pierwszych.

Można by pomyśleć, że choć trudno sprawdzić, czy liczba jest pierwsza, to może łatwo wymyślić jakieś liczby pierwsze albo przynajmniej, że w pewnych szczególnych przypadkach sprawdzenie pierwszości jest łatwiejsze. I tak faktycznie jest. Dla liczb Mersenne’a (tj. takich postaci \(2^n-1\)) możemy zastosować test pierwszości Lucasa–Lehmera. Niestety znamy tylko 49 liczb pierwszych Mersenne’a, a to stanowczo za mało aby szyfr był trudny do złamania (wymyślone liczby pierwsze powinny być tajne, więc użycie liczb pierwszych Mersenne’a byłoby trochę jak użycie jednoliterowego hasła). Dlatego też stosuje się tzw. algorytmy probabilistyczne, tj. takie, które mogą czasem udzielić złej odpowiedzi. Można więc powiedzieć, że bezpieczeństwo bankowe zależy od szczęścia. Jednak prawdopodobieństwo popełnienia błędu możemy kontrolować, tzn. jeśli uznamy, że jest ono za duże, możemy je zmniejszyć, kosztem dłuższego czasu działania algorytmu. W tym artykule chciałbym przedstawić wykorzystanie ciągu Fibonacciego do sprawdzenia pierwszości liczby, co fachowo jest nazywane testem pierwszości Frobeniusa dla wielomianu \(x^2-x-1\).

Ciąg Fibonacciego

Dawno temu pewien człowiek, Leonard z Pizy, postanowił spróbować ,,zamodelować” sposób, w jaki rozmnażają się króliki. Założenia tego modelu były następujące. W pierwszym miesiącu mamy jedną parę młodych królików. W drugim gryzonie dorastają i od trzeciego miesiąca co miesiąc wydają na świat parę królików. Te dorastają, rodzą kolejne króliki, itd. Tak więc w pierwszym miesiącu mamy jedną młodą parę gryzoni. W drugim — jedną dojrzałą parę. W trzecim mamy już jedną dojrzałą i jedną młodą. Liczby par królików w każdym kolejnym miesiącu tworzą ciąg, znany jako ciąg Fibonacciego. Jego kilka pierwszych wyrazów ma następującą postać

Pierwsze pytanie, jakie przychodzi do głowy, brzmi ,,jak opisać ten ciąg w zwięzły sposób”. To akurat jest dość proste. Wiemy, że dojrzałych par jest tyle, ile było wszystkich par miesiąc wcześniej, a młodych — tyle, ile było dojrzałych par miesiąc wcześniej, czyli tyle, ile było wszystkich par dwa miesiące temu. Możemy zatem zapisać
\[
F_n=F_{n-1}+F_{n-2},
\]
lub równoważnie:
\[
F_{n+2}=F_{n+1}+F_n,
\]
co po dodaniu warunków początkowych
\[
F_1=F_2=1,
\]
daje nam krótki opis ciągu².

Czy ciąg \((F_n)\) da się opisać takim wzorem, który nie odwołuje się do samego siebie? Okazuje się, że tak, choć wzór jest nieco bardziej złożony niż mogło by się wydawać. Dość powiedzieć, że został on wymyślony ponad 600 lat po opisaniu ciągu przez Leonarda.

Spójrzmy na ilorazy kolejnych par wyrazów

Wydaje się, że ciąg ilorazów jest zbieżny (tzn. jego wartości dążą do jakiejś liczby). Oznacza to tyle, że ciąg Fibonacciego zachowuje się mniej więcej jak ciąg geometryczny. Oczywiście nie jest to do końca prawda, ale jako pierwsze przybliżenie to całkiem sensowny pomysł. Tak więc \(F_n\approx a\cdot b^n\). Jak oszacować \(a\) i \(b\)? Wiemy, że:
\[
F_{n+2}=F_{n+1}+F_n,
\]
a więc:
\begin{align*}
a\cdot b^{n+2} & \approx a\cdot b^{n+1}+a\cdot b^n,\\
b^2 & \approx b+1.
\end{align*}
Otrzymaliśmy równanie kwadratowe, którego rozwiązanie prezentujemy poniżej:
\[
b_1=\frac{1+\sqrt{5}}{2}\approx 1{,}618,\quad b_2=\frac{1-\sqrt{5}}{2}\approx -0{,}618.
\]
Może się wydawać, że powinniśmy wybrać \(b_1\) jako że ciąg ilorazów dąży do \(b_1\). Okazuje się jednak, że należy wybrać… oba rozwiązania. Mówiąc ściślej, ciąg Fibonacciego jest sumą dwóch ciągów geometrycznych. Zatem:
\[
F_n=a_1b_1^n+a_2b_2^n.
\]
Pozostaje obliczyć \(a_1\) i \(a_2\). Do tego wystarczy podstawić pod powyższe równanie \(n=0\) i \(n=1\). W ten sposób otrzymamy wzór:
\[
F_n = \frac{1}{\sqrt 5}\left(\frac{1 + \sqrt 5}{2}\right)^n – \frac{1}{\sqrt 5}\left(\frac{1 – \sqrt 5}{2}\right)^n.
\]

Pomocnicze fakty

W dalszej częsci potrzebować będziemy kilku nowych pojęć. Funkcja \(x\mapsto \lfloor x \rfloor\) nazywana jest częścią całkowitą bądź podłogą liczby \(x\) — jest to największa liczba całkowita nie większa od \(x\). Przydadzą się nam też silnia i dwumian Newtona, które definiuje się odpowiednio:
\begin{align*}
n! & =1\cdot 2\cdot 3\cdot\dots\cdot n,\\
\binom{n}{k} & =\frac{n!}{k!(n-k)!}.
\end{align*}
Korzystać będziemy również ze skróconego zapisu sum. Do tego użyjemy
symbolu \(\sum\). Oznacza ona sumę pewnej liczby składników, np.:
\[
\sum_{k=a}^b f(k)=f(a)+f(a+1)+f(a+2)+\dots +f(b).
\]
Jak widać, symbol sumy służy do skrócenia zapisu. Pozbywamy się też wielokropka, który czasami można różnie rozumieć. Krótka dygresja. Kiedyś spotkałem się z takim oto zapisem:
\[
f(1)+f(2)+\dots+f(2^n).
\]
Na pierwszy rzut oka wydawało się, że chodzi o sumę wartości funkcji dla wszystkich liczb całkowitych z przedziału od \(1\) do \(2^n\), czyli:
\[
f(1)+f(2)+f(3)+f(4)+\dots+f(2^n).
\]
Jednak autorowi chodziło o sumę wartości funkcji jedynie dla potęg dwójki, czyli:
\[
f(1)+f(2)+f(4)+f(8)+\dots +f(2^n).
\]
Zapis przy użyciu \(\sum\) pozwala uniknąć nieporozumień:
\begin{align*}
\sum_{k=1}^{2^n} f(n) & = f(1)+f(2)+f(3)+f(4)+\dots+f(2^n),\\
\sum_{k=1}^{n} f(2^n) & =f(1)+f(2)+f(4)+f(8)+\dots +f(2^n).
\end{align*}

Liczby pierwsze i ciąg Fibonacciego

Pora wrócić do naszego ciągu. Wzór ogólny możemy przekształcić, korzystając ze wzoru dwumiennego \((a+b)^n=\sum_{k=0}^n \binom{n }{ k}a^kb^{n-k}\):
\begin{align*}
(a+b)^n & =\binom{n }{ 0}a^nb^0+\binom{n}{1}a^{n-1}b^1+\dots+\binom{n}{n}a^0b^n,\\
-(a-b)^n & =-\binom{n }{ 0}a^nb^0+\binom{n}{1}a^{n-1}b^1-\dots+(-1)^{n+1}\binom{n}{n}a^0b^n.
\end{align*}
Możemy te równania dodać stronami. Wtedy około połowa wyrazów skróci się i otrzymamy:
\[
(a+b)^n-(a-b)^n=2\binom{n}{1}a^{n-1}b^1+2\binom{n}{3}a^{n-3}b^3+\dots+(1+(-1)^{n+1})\binom{n}{n}a^{0}b^n.
\]
Przy użyciu symbolu sumy zapis będzie wyglądał tak:
\[(a+b)^n-(a-b)^n=2\sum_{k=0}^{\lfloor (n-1)/2\rfloor} \binom{n}{2k+1}a^{2k+1}b^{n-2k-1}.
\]
Możemy wykorzystać to do przekształcenia wzoru na \(F_n\).
\begin{align*}
F_n & = \frac{1}{2^n\sqrt 5}\left[\left(1 + \sqrt 5\right)^n – \left(1 – \sqrt 5\right)^n\right]\\
& =\frac{1}{2^n\sqrt 5}\left[\sum_{k=0}^{\lfloor (n-1)/2\rfloor } 2\binom{n }{ 2k+1}\sqrt{5}^{2k+1}\right]\\
& = \frac{1}{2^{n-1}}\sum_{k=0}^{\lfloor (n-1)/2\rfloor } \binom{n }{ 2k+1}5^{k}.
\end{align*}

Jak na razie nie widać na horyzoncie co ten ciąg ma wspólnego z liczbami pierwszymi. Otóż okazuje się, że jeśli \(p\) jest liczbą pierwszą, to prawie zawsze zachodzi jeden z dwóch warunków:

• \(p\) jest dzielnikiem \(F_{p-1}\) oraz \(F_p-1\),
• \(p\) jest dzielnikiem \(F_{p+1}\) oraz \(F_p+1\).

Jest tylko jeden wyjątek: dla \(p=5\) nie zachodzi żaden z tych dwóch warunków. Ponadto, pierwszy warunek zachodzi wtedy, gdy ostatnią cyfrą \(p\) jest \(1\) lub \(9\). Gdy ostatnią cyfrą jest \(2\), \(3\) lub \(7\), zachodzi warunek drugi.

Spróbujemy teraz pokazać, że tak faktycznie jest. Zastosujemy zapis
\[
a\equiv b \pmod{c},
\]
(czyt. ,,a przystaje do b modulo c”), gdy \(a\) i \(b\) mają tę samą resztę z dzielenia przez c. Nieprzypadkowo ,,\(\equiv\)” przypomina ,,\(=\)”. Przystawanie (zwane też kongruencją) można (do pewnego stopnia) traktować jak równość, co wiąże się z tym, że można wykonywać obustronnie operacje matematyczne (dodawanie, odejmowanie, mnożenie). Można także dodawać i mnożyć kongruencje stronami. Dla przykładu, jeśli \(a\equiv b \pmod{n}\) oraz \(c\equiv d \pmod{n}\), to \(ac\equiv bd \pmod{n}\). Nie wolno jednak łączyć ze sobą w żaden sposób kongruencji \(a\equiv b \pmod{n}\) i \(c\equiv d \pmod{m}\), jeśli \(n\neq m\). Jeśli chodzi o dzielenie, należy zachować pewną ostrożność. Kongruencję \(ad\equiv bd \pmod{n}\) możemy skrócić do \(a\equiv b \pmod{n}\) pod warunkiem, że \(d\) i \(n\) są względnie pierwsze. Komfortowa sytuacja jest wtedy, gdy \(n\) jest liczbą pierwszą. Wtedy możemy dzielić przez dowolną liczbę, która nie jest wielokrotnością \(n\). Można to uargumentować w ten sposób, że \(kn\equiv 0 \pmod{n}\), więc dzielenie przez \(kn\) jest równoważne dzieleniu przez \(0\) (a więc niedozwolone).

Wyposażeni w podstawową wiedzę o kongruencjach, możemy przystąpić do policzenia reszty z dzielenia \(F_p\) przez \(p\), gdzie \(p\) jest liczbą pierwszą. Przyjmijmy najpierw, że \(p\) nie jest równe \(2\) ani \(5\).
\[
F_p=\frac{1}{2^{p-1}}\sum_{k=0}^{\lfloor (p-1)/2\rfloor } \binom{p }{ 2k+1}5^{k}.
\]
Wzór wygląda dość groźnie, ale za chwilę się okaże, że nie jest aż tak źle. Po pierwsze — dobrze jest pozbyć się operacji dzielenia. Pomoże nam w tym słynny matematyk, niejaki Pierre de Fermat i twierdzenie, które udowodnił — tzw. małe twierdzenie Fermata. Orzeka ono, że jeśli \(p\) jest liczbą pierwszą, to:
\[
a^p\equiv a \pmod{p}.
\]
Jeśli \(a\) nie jest wielokrotnością \(p\), to możemy podzielić to równanie przez \(a\), otrzymując, że \(a^{p-1}\equiv 1 \pmod{p}\), więc w szczególności \(2^{p-1}\equiv 1 \pmod{p}\) dla \(p\) różnego od \(2\). Ponadto jeśli \(p\) jest nieparzyste, to \((p-1)/2\) jest całkowite, zatem możemy pozbyć się funkcji podłogi.
\[
F_p=\frac{1}{2^{p-1}}\sum_{k=0}^{\lfloor (p-1)/2\rfloor } \binom{p }{ 2k+1}5^{k}\equiv \frac{1}{1}\sum_{k=0}^{(p-1)/2} \binom{p }{ 2k+1}5^{k}\pmod{p}.
\]
Teraz pora zająć się dwumianem. Pokażemy, że w tej sumie jest on prawie zawsze wielokrotnością \(p\).
\[
\binom{p}{ 2k+1}=\frac{p!}{(2k+1)!(p-2k-1)!}.
\]
Licznik oczywiście jest podzielny przez \(p\). Ponadto \((p-2k-1)!=1\cdot 2\cdot\dots\cdot (p-2k-1)\) nie jest podzielne przez \(p\), ponieważ wszystkie czynniki są mniejsze niż \(p\). Z tego samego powodu \((2k+1)!\) jest wielokrotnością \(p\) tylko gdy \(2k+1\ge p\). W naszej sumie jest tylko jeden taki składnik — gdy \(k=(p-1)/2\). Wielokrotności \(p\) wewnątrz sumy możemy pomijać, ponieważ przystają one do \(0\). Zatem mamy:
\begin{align*}
F_p & \equiv\sum_{k=0}^{(p-1)/2} \binom{p }{ 2k+1}5^{k}\\
& \equiv\binom{p}{ p} 5^{(p-1)/2}+\sum_{k=0}^{(p-1)/2-1} \binom{p }{ 2k+1}5^{k}\\
& \equiv \binom{p}{ p} 5^{(p-1)/2}\\
& \equiv 5^{(p-1)/2}\pmod{p}.
\end{align*}
Ponieważ \((5^{(p-1)/2}-1)(5^{(p-1)/2}+1)=5^{p-1}-1\equiv 0 \pmod{p}\) (ostatnia kongruencja zachodzi na mocy małego twierdzenia Fermata), zatem \(p\) jest dzielnikiem jednego z tych dwóch czynników. Stąd \(F_p\equiv\pm 1 \pmod{p}\). Podobnie możemy się uporać z \(F_{p+1}\). Tym razem rachunki są nieco bardziej skomplikowane, ponieważ aż dwa składniki sumy są niepodzielne przez \(p\) — pierwszy i ostatni.
\begin{align*}
F_{p+1} & =\frac{1}{2^{p}}\sum_{k=0}^{\lfloor p/2\rfloor } \binom{p+1 }{ 2k+1}5^{k}\\
& \equiv\frac{1}{2}\sum_{k=0}^{(p-1)/2} \binom{p+1 }{ 2k+1}5^{k}\\
& \equiv\frac{1}{2}\left( \binom{p+1 }{ 2\cdot 0+1}5^0+\binom{p+1 }{ p-1+1}5^{\frac{p-1}{2}}\right)\\
& \equiv \frac{1}{2}\left( \binom{p+1 }{ 1}5^0+\binom{p+1 }{ p}5^{\frac{p-1}{2}}\right)\\
& \equiv\frac{1}{2}\left( (p+1)5^0+(p+1)5^{\frac{p-1}{2}}\right)\\
& \equiv \frac{5^0+5^\frac{p-1}{2}}{2} \pmod{p}.
\end{align*}
Stąd wynika, że jeśli \(F_p\equiv 1\pmod{p}\), to \(F_{p+1}\equiv \frac{1+1}{2}\equiv 1\pmod{p}\), a jeśli \(F_p\equiv-1\pmod{p}\), to \(F_{p+1}\equiv \frac{1-1}{2}=0\pmod{p}\).

Aby ustalić, kiedy \(F_{p}\equiv 1\pmod{p}\), a kiedy \(F_{p}\equiv -1\pmod{p}\), musimy umieć policzyć \(5^{(p-1)/2}\). Gdyby udało się znaleźć taką liczbę \(a\), że \(5\equiv a^2\pmod{p}\), wtedy \(5^{(p-1)/2}\equiv (a^2)^{(p-1)/2}\equiv a^{p-1}\equiv 1\pmod{p}\). Nieco mniej prostym do pokazania jest stwierdzenie odwrotne do podanego (czyli że jeśli \(5^{(p-1)/2}\equiv 1\pmod{p}\), to \(5=a^2\pmod{p}\). Przyjrzyjmy się jak to wygląda dla jakiegoś ustalonego \(p\), powiedzmy \(p=7\). Będziemy rozważać liczby z przedziału \([1,6]\), ponieważ wiemy, że w razie konieczności czego liczby możemy zmniejszyć, np. \(20\equiv 6\pmod{7}\). %Ponadto \(0\) nas w tej chwili niespecjalnie interesuje.

Wprawne oko dostrzeże, że druga kolumna jest palindromem, czyli nie zmieni się po odwróceniu kolejności. Czy tak jest dla każdej liczby pierwszej? Otóż tak. Zauważmy, że \(1\) i \(6\) są liczbami przeciwnymi, tzn. \(1\equiv -6 \pmod{7}\). Stąd
\[
1^2\equiv(-6)^2\equiv(-1\cdot 6)^2\equiv (-1)^2\cdot 6^2\equiv 6^2\pmod{7}.
\]
Podobnie rozumowanie można przeprowadzić dla drugiej i przedostatniej liczby itd. Podobnie też można zrobić to dla dowolnej liczby pierwszej. Z drugiej strony jeśli \(a^2\equiv b^2\pmod{p}\), to \((a-b)(a+b)\) dzieli się przez \(p\). Oznacza to, że \(a\equiv b\pmod{p}\) lub \(a\equiv -b\pmod{p}\). Zatem nie dość, że druga kolumna jest palindromem, to ma tę własność, że żadna liczba nie pokaże się więcej niż dwa razy. Ponieważ założyliśmy, że \(p\neq 2\), a palindrom ma długość \(p-1\), zatem jego długość jest parzysta. Oznacza to tyle, że nie zawiera pojedynczej liczby, która występowałaby w jego środku. A więc reszt kwadratowych modulo \(p\) jest dokładnie \((p-1)/2\). Z drugiej strony rozważmy równanie \(x^{(p-1)/2}-1\equiv 0 \pmod{p}\). W świecie reszt modulo \(p\) (gdzie \(p\) jest pierwsze) istnieje prawo znane ze świata liczb rzeczywistych. Wielomian stopnia \(n\) (gdzie stopniem wielomianu jest najwyższa potęga przy \(x\)) może mieć co najwyżej \(n\) rozwiązań. Wiemy, że każda reszta kwadratowa (za wyłączeniem 0) jest rozwiązaniem powyższego równania, ponadto reszt kwadratowych (znów, za wyłączeniem \(0\)) jest \((p-1)/2\), czyli dokładnie tyle, ile wynosi stopień tego wielomianu. Wynika z tego, że nie ma miejsca już na żadną liczbę, która chciałaby spełniać to równanie, a nie jest resztą kwadratową.

Teraz pora na twierdzenie, które rozstrzygnie, kiedy \(5\) jest resztą kwadratową modulo \(p\), a kiedy nie jest. Nazywa się ono twierdzeniem o wzajemności reszt kwadratowych. Mówi ono, że jeśli \(p\) i \(q\) są nieparzystymi liczbami pierwszymi oraz co najmniej jedna z liczb \(p\) i \(q\) jest postaci \(4k+1\), to zachodzi następująca równoważność: \(p\) jest resztą kwadratową modulo \(q\) wtedy i tylko wtedy, gdy \(q\) jest resztą kwadratową modulo \(p\).

Ponadto, gdy żadna z liczb pierwszych nie jest postaci \(4k+1\) (obie są postaci \(4k+3\)), to jest na odwrót, tzn. jeśli \(p\) jest resztą kwadratową modulo \(q\), wtedy i tylko wtedy, gdy \(q\) nie jest resztą kwadratową modulo \(p\). %Formalnie wygląda to tak:

Wróćmy do naszego problemu. \(5=4\cdot1+1\), a zatem 5 jest resztą kwadratową modulo \(p\) wtedy i tylko wtedy, gdy \(p\) jest resztą kwadratową modulo 5. To zaś jest łatwo sprawdzić. Jedynymi resztami kwadratowymi modulo 5 (poza 0) są \(1\equiv 1^2\equiv 4^2\pmod{5}\) i \(4\equiv 2^2\equiv 3^2 \pmod{5}\).

Zbierzmy teraz wszystko w całość. Wiemy, jak wyglądają reszty \(F_p\) i \(F_{p+1}\) gdy \(p\) jest pierwsze. Teoretycznie jednak jakaś liczba złożona może się ,,podszyć” pod liczbę pierwszą. Tak więc ciąg Fibonacciego powie nam, że liczba jest złożona lub że jest prawdopodobnie pierwsza. Test pierwszości oparty o ten ciąg wygląda tak.

1. Jeśli \(p\equiv 1,4\pmod{5}\), to sprawdź, czy \(F_p\equiv 1 \pmod{p}\) oraz \(F_{p+1}\equiv 1\pmod{p}\). Jeśli nie, liczba jest złożona. Jeśli tak, to prawdopodobnie jest pierwsza.
2. Jeśli \(p\equiv 2,3\pmod{5}\), to sprawdź, czy \(F_p\equiv -1\pmod{p}\) oraz \(F_{p+1}\equiv 0\pmod{p}\). Jeśli nie, liczba jest złożona. Jeśli tak, to prawdopodobnie jest pierwsza.
3. Jeśli \(p\equiv 0\pmod{5}\), sprawdź czy \(p=5\). Jeśli tak, liczba jest pierwsza, jeśli nie — złożona.

No dobrze, ale to nie daje nam pewności, czy liczba jest pierwsza. Co prawda trudno mieć zupełną pewność, ale dobrze byłoby umieć dowolnie zmniejszać szanse na popełnienie błędu. W tym celu można użyć ciągów o wzorze ogólnym \(C_{n}=aC_{n-1}+bC_{n-2}\) podstawiając różne wartości \(a\) i \(b\). Za pomocą takich ciągów da się w podobny sposób sprawdzać, czy liczba jest pierwsza. Jeśli wykonamy kilka takich testów pierwszości, to możemy być niemal pewni odpowiedzi na pytanie ,,czy liczba jest pierwsza”.

Obliczanie \(F_p\)

Pozostaje jeden problem. Skoro wykorzystujemy liczbę \(F_p\) do badania pierwszości \(p\), to przydałoby się umieć ją obliczyć w sensownym czasie (tzn. szybciej niż sprawdzać po kolei czy \(p\) dzieli się przez jakąś liczbę z przedziału \([2,\sqrt{p}]\)). W tym celu przydaje się zdefiniować iloczyn macierzy. W ogólności macierz to prostokąt o wymiarach \(n \times m\), ale nam wystarczą macierze \(2 \times 2\). Wtedy mnożenie można opisać takim wzorem:
\[
\left(\begin{matrix}
a_{11} & a_{12}\\
a_{21} & a_{22}
\end{matrix}
\right)\cdot \left(\begin{matrix}
b_{11} & b_{12}\\
b_{21} & b_{22}
\end{matrix}
\right)=\left(\begin{matrix}
a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22}\\
a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22}
\end{matrix}
\right).
\]
Innymi słowy, aby obliczyć np. wyraz w \(i\)-tym wierszu \(i\) w \(j\)-tej kolumnie wyniku, należy pomnożyć skalarnie \(i\)-ty wiersz pierwszej macierzy oraz \(j\)-ty wiersz drugiej macierzy, gdzie iloczyn skalarny jest dany wzorem:
\[
[a_1,a_2]\cdot [b_1,b_2]=a_1b_1+a_2b_2.
\]
Mnożenie macierzy ma pewną własność, która okaże się dla nas istotna — jest łączne. To znaczy, że jeśli mamy policzyć iloczyn kilku macierzy, to nie ma znaczenia, czy najpierw będziemy mnożyć macierze po lewej, po prawej czy w środku.

Zauważmy, że:
\[\left(\begin{matrix}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{matrix}
\right)\cdot
\left(\begin{matrix}
1 & 1\\
1 & 0
\end{matrix}\right)=\left(\begin{matrix}
F_{n+1}+F_n & F_{n+1}\\
F_{n}+F_{n-1} & F_{n}
\end{matrix}
\right)=\left(\begin{matrix}
F_{n+2} & F_{n+1}\\
F_{n+1} & F_{n}
\end{matrix}
\right).\]
Oznaczmy \(M_n=\left(\begin{matrix}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{matrix}
\right)\), \(A=\left(\begin{matrix}
1 & 1\\
1 & 0
\end{matrix}\right)\). Wtedy \(M_{n+1}=A\cdot M_{n}\), \(M_1=A\). Stąd łatwo wywnioskować, że \(M_{n}=A^n\).

Co to nam daje? Zastanówmy się jak obliczyć np. \(A^{100}\) wiedząc, ile wynosi \(A\). Oczywiście możemy po kolei wyliczać \(A^2, A^3, A^4,\dots, A^{100}\). Ale możemy to zrobić również tak:
\begin{align*}
A\cdot A & =A^2,\\
A^2\cdot A & =A^3,\\
A^3\cdot A^3 & =A^6,\\
A^6\cdot A^6 & =A^{12},\\
A^{12}\cdot A^{12} & =A^{24},\\
A^{24}\cdot A & =A^{25},\\
A^{25}\cdot A^{25} & =A^{50},\\
A^{50}\cdot A^{50} & =A^{100}.
\end{align*}
W ten sposób wykonaliśmy tylko 9 operacji na macierzach (zamiast 99). Dla większych potęg różnica ta jest jeszcze większa.

Przypisy

1. Czytelnikowi zainteresowanemu liczbami pierwszymi polecamy również tekst Karola Gierszewskiego Divide et impera.
2. Taki zapis nazywamy rekurencyjnym

---

Artykuł został przygotowany przy wsparciu pozyskanemu przez Poznańską Fundację Matematyczną od Miasta Poznań na realizację projektu ,,Potęga matematyki''.