Let \(p=398874989\) and \(G=p^2-1\). The computation is carried out in the two-dimensional algebra
$$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$$
where \(u\) plays the role of \(\sqrt5\). For the Fibonacci numbers
$$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2},$$
define the reduced exponent
$$e_n\equiv 5^{F_n}\pmod G.$$
If
$$\beta^{e_n}=a_n+b_nu,$$
then the \(n\)-th contribution is
$$s_n=b_n^5+(-a_n)^5\pmod p.$$
The goal is to evaluate
$$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p.$$
Directly forming the Fibonacci exponents is hopeless. The successful approach is to keep only a short modular exponent recurrence and to evaluate powers of \(\beta\) inside the fixed algebra \(R\).
The three implementations all exploit the same structure: the golden-looking base \(\sqrt5-2\), the multiplicative behavior of \(5^{F_n}\), and the fact that every relevant power can be reconstructed from a 64-entry binary table.
The algebra \(R\) is represented in the basis \(1,u\) with \(u^2=5\). Multiplication is therefore
$$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p.$$
This is exactly the rule used by the implementations. It keeps every power of \(\beta\) in the form \(a+bu\), so the final summand is obtained by reading off two coefficients.
The adjective "golden" is not cosmetic. If
$$\phi=\frac{1+\sqrt5}{2},$$
then \(\phi^3=2+\sqrt5\), hence
$$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$$
Also,
$$\left(u-2\right)\left(u+2\right)=u^2-4=1,$$
so \(\beta\) is a unit of the algebra and every positive power is well-defined.
For this specific prime, \(p\equiv 4\pmod 5\). Since \(5\equiv 1\pmod 4\), quadratic reciprocity gives \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\), so \(u^2-5\) splits over \(\mathbb{F}_p\). In other words, \(R\) is a split quadratic algebra, isomorphic to \(\mathbb{F}_p\times\mathbb{F}_p\). The code does not need that isomorphism explicitly; the coefficient basis \(1,u\) is already enough.
The Fibonacci recurrence immediately gives
$$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$$
Because \(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\), every unit has multiplicative period dividing \(p-1\). So any multiple of \(p-1\) is a safe modulus for exponents. The implementations use the larger quantity
$$G=p^2-1=(p-1)(p+1),$$
which is not minimal but is still perfectly valid because \(p-1\mid G\).
That lets us replace the astronomical integer \(5^{F_n}\) by the residue
$$e_n\equiv 5^{F_n}\pmod G.$$
The residues satisfy the compact recurrence
$$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3).$$
This is the decisive simplification. Instead of carrying Fibonacci numbers or giant exponentials, the algorithm advances the entire exponent side with one modular multiplication per step.
The algebra has an involution \(u\mapsto -u\), so
$$\overline{a+bu}=a-bu.$$
The associated norm is
$$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p.$$
For the base element \(\beta=u-2\),
$$N(\beta)=(u-2)(-u-2)=4-u^2=-1.$$
Every \(e_n\) is odd: the sequence starts from \(5,5\), and modulo the even number \(G\) the product of odd residues remains odd. Therefore
$$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$$
So if
$$\beta^{e_n}=a_n+b_nu,$$
then the coefficients always satisfy
$$a_n^2-5b_n^2\equiv -1\pmod p.$$
This Pell-type congruence is not the final answer, but it explains the shape of every coefficient pair and provides a clean mathematical consistency check.
Starting from \(\beta=u-2\), repeated multiplication gives
$$\beta^1=-2+u,$$
$$\beta^2=9-4u,$$
$$\beta^3=-38+17u,$$
$$\beta^4=161-72u,$$
$$\beta^5=-682+305u.$$
The tiny checkpoint at exponent \(1\) is
$$s(1)=1^5+2^5=33,$$
because \(\beta^1=-2+u\). The actual sum begins at \(n=2\), where \(e_2=5\), so the first accumulated term is
$$s_2=305^5+682^5\equiv 257933744\pmod p.$$
The next reduced exponent is
$$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G,$$
and evaluating \(\beta^{25}\) in the same basis gives
$$s_3\equiv 26500067\pmod p.$$
Those two values are exactly the small checkpoints embedded in the implementations. After that, the same recurrence-and-powering pattern continues all the way to \(n=1{,}618{,}034\).
Each algebra element is stored as a pair of residues \((a,b)\) representing \(a+bu\). Multiplication uses the formula above, so every operation stays in two coordinates modulo \(p\). The quantity \((-a)^5\) is computed modulo \(p\) as the fifth power of the additive inverse of the first coordinate.
The C++, Python, and Java implementations precompute
$$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$$
by repeated squaring. That table is sufficient because the chosen exponent modulus satisfies \(0\le e_n<G<2^{64}\). Any required power \(\beta^{e_n}\) is then reconstructed from the binary expansion of \(e_n\).
The implementations never materialize a Fibonacci number. They keep only the two latest exponent residues, both initially equal to \(5\). The answer is initialized with the \(n=2\) term, and then for each \(n\ge 3\) they compute
$$e_n\equiv e_{n-1}e_{n-2}\pmod G,$$
rebuild \(\beta^{e_n}\) from the binary table, extract \(a_n\) and \(b_n\), evaluate \(b_n^5+(-a_n)^5\pmod p\), and add it to the running sum. The three language versions differ only in low-level modular-multiplication details; the mathematical pipeline is identical.
Let \(M=1{,}618{,}034\). Precomputing the binary table costs \(64\) algebra multiplications. Each subsequent term uses one modular multiplication for the exponent recurrence and at most \(64\) algebra multiplications to reconstruct \(\beta^{e_n}\) from its bits. Therefore the running time is
$$O(M\log G),$$
and since \(\log G<64\), this is effectively linear in the number of required indices.
The memory usage is \(O(1)\): a constant-size power table, two current exponents, a running total, and a few temporary algebra elements.
Setze \(p=398874989\) und \(G=p^2-1\). Gerechnet wird in der zweidimensionalen Algebra
$$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$$
wobei \(u\) die Rolle von \(\sqrt5\) spielt. Fur die Fibonacci-Zahlen
$$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2}$$
definieren wir den reduzierten Exponenten
$$e_n\equiv 5^{F_n}\pmod G.$$
Schreibt man
$$\beta^{e_n}=a_n+b_nu,$$
dann lautet der Beitrag des Index \(n\)
$$s_n=b_n^5+(-a_n)^5\pmod p.$$
Gesucht ist also
$$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p.$$
Eine direkte Rechnung mit den Fibonacci-Exponenten ist ausgeschlossen. Die Lösung funktioniert nur, weil die riesigen Exponenten auf eine kurze modulare Rekurrenz reduziert werden und weil Potenzen von \(\beta\) stets in der festen Algebra \(R\) bleiben.
Alle drei Implementierungen nutzen dieselbe Struktur: das goldene Basiselement \(\sqrt5-2\), das multiplikative Verhalten von \(5^{F_n}\) und eine binäre Potenztabelle mit nur 64 Einträgen.
Die Algebra \(R\) wird in der Basis \(1,u\) mit \(u^2=5\) dargestellt. Daher gilt fur die Multiplikation
$$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p.$$
Genau diese Formel wird in den Implementierungen verwendet. Jede Potenz von \(\beta\) bleibt also von der Form \(a+bu\), und der Summand ergibt sich unmittelbar aus den beiden Koeffizienten.
Der Bezug zum goldenen Schnitt ist echt. Mit
$$\phi=\frac{1+\sqrt5}{2}$$
gilt \(\phi^3=2+\sqrt5\) und damit
$$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$$
Außerdem ist
$$\left(u-2\right)\left(u+2\right)=u^2-4=1,$$
also ist \(\beta\) eine Einheit der Algebra.
Fur dieses spezielle Primzahlmodul gilt \(p\equiv 4\pmod 5\). Weil \(5\equiv 1\pmod 4\), liefert das quadratische Reziprozitatsgesetz \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\). Damit zerfallt \(u^2-5\) bereits uber \(\mathbb{F}_p\), also ist \(R\) eine gesplittete quadratische Algebra, isomorph zu \(\mathbb{F}_p\times\mathbb{F}_p\). Die Implementierungen brauchen diesen Isomorphismus nicht explizit; die Koeffizientendarstellung in der Basis \(1,u\) reicht vollstandig aus.
Aus der Fibonacci-Rekurrenz folgt sofort
$$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$$
Da \(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\) gilt, hat jede Einheit eine multiplikative Periode, die \(p-1\) teilt. Also ist jedes Vielfache von \(p-1\) ein sicherer Exponentenmodul. Die Implementierungen verwenden die größere Zahl
$$G=p^2-1=(p-1)(p+1),$$
die nicht minimal, aber vollkommen korrekt ist, weil \(p-1\mid G\) gilt.
So wird aus dem astronomischen Exponenten \(5^{F_n}\) nur noch der Rest
$$e_n\equiv 5^{F_n}\pmod G.$$
Diese Reste erfullen die kompakte Rekurrenz
$$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3).$$
Das ist die entscheidende Vereinfachung: Anstelle riesiger Fibonacci-Exponenten braucht der Algorithmus pro Schritt nur eine einzige modulare Multiplikation.
Die Algebra besitzt die Involution \(u\mapsto -u\), also
$$\overline{a+bu}=a-bu.$$
Die zugehorige Norm ist
$$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p.$$
Fur das Basiselement \(\beta=u-2\) ergibt sich
$$N(\beta)=(u-2)(-u-2)=4-u^2=-1.$$
Alle \(e_n\) bleiben ungerade: Die Folge startet mit \(5,5\), und modulo der geraden Zahl \(G\) bleibt das Produkt zweier ungerader Reste wieder ungerade. Daher
$$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$$
Wenn also
$$\beta^{e_n}=a_n+b_nu,$$
dann gilt stets
$$a_n^2-5b_n^2\equiv -1\pmod p.$$
Diese Pell-artige Kongruenz ist nicht die Endsumme, aber sie beschreibt die Geometrie aller Koeffizientenpaare und liefert eine starke Plausibilitatskontrolle.
Von \(\beta=u-2\) aus liefert wiederholtes Multiplizieren
$$\beta^1=-2+u,$$
$$\beta^2=9-4u,$$
$$\beta^3=-38+17u,$$
$$\beta^4=161-72u,$$
$$\beta^5=-682+305u.$$
Der kleinste Kontrollwert ist der Exponent \(1\): Aus \(\beta^1=-2+u\) folgt
$$s(1)=1^5+2^5=33.$$
Die eigentliche Summe beginnt bei \(n=2\), also bei \(e_2=5\). Deshalb ist der erste aufsummierte Beitrag
$$s_2=305^5+682^5\equiv 257933744\pmod p.$$
Der nächste reduzierte Exponent ist
$$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G,$$
und die Auswertung von \(\beta^{25}\) in derselben Basis ergibt
$$s_3\equiv 26500067\pmod p.$$
Genau diese Werte erscheinen als kleine Kontrollpunkte in den Implementierungen. Danach wird dieselbe Rekurrenz-Potenzierungs-Struktur bis \(n=1{,}618{,}034\) fortgesetzt.
Jedes Algebraelement wird als Koeffizientenpaar \((a,b)\) fur \(a+bu\) gespeichert. Die Multiplikation benutzt die obige Formel, sodass jede Operation in zwei Koordinaten modulo \(p\) bleibt. Die GroBe \((-a)^5\) wird modulo \(p\) als funfte Potenz des additiven Inversen der ersten Koordinate berechnet.
Die C++-, Python- und Java-Implementierungen berechnen vorab
$$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$$
durch wiederholtes Quadrieren. Diese Tabelle genügt, weil fur den gewahlten Modulus immer \(0\le e_n<G<2^{64}\) gilt. Jede benötigte Potenz \(\beta^{e_n}\) wird anschließend uber die Binardarstellung von \(e_n\) rekonstruiert.
Es wird nie eine Fibonacci-Zahl selbst gespeichert. Stattdessen halten die Implementierungen nur die beiden letzten Exponentenreste, anfangs beide gleich \(5\). Die Summe wird mit dem Term fur \(n=2\) initialisiert, und danach wird fur jedes \(n\ge 3\)
$$e_n\equiv e_{n-1}e_{n-2}\pmod G$$
berechnet, \(\beta^{e_n}\) aus der Binar-Tabelle aufgebaut, \(a_n\) und \(b_n\) ausgelesen, \(b_n^5+(-a_n)^5\pmod p\) gebildet und zum laufenden Ergebnis addiert. Die drei Sprachversionen unterscheiden sich nur in den Details der modularen Arithmetik, nicht in der Mathematik.
Sei \(M=1{,}618{,}034\). Das Vorberechnen der Binar-Tabelle kostet \(64\) Algebra-Multiplikationen. Jeder weitere Term benötigt eine modulare Multiplikation fur die Exponentenrekurrenz und höchstens \(64\) Algebra-Multiplikationen, um \(\beta^{e_n}\) aus seinen Bits aufzubauen. Damit ergibt sich
$$O(M\log G),$$
und weil \(\log G<64\), ist das praktisch linear in der Anzahl der benotigten Indizes.
Der Speicherbedarf ist \(O(1)\): eine Potenztabelle konstanter Größe, zwei aktuelle Exponenten, eine laufende Summe und einige temporare Algebraelemente.
\(p=398874989\) ve \(G=p^2-1\) olsun. Hesaplar
$$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$$
iki boyutlu cebirinde yapilir; burada \(u\), \(\sqrt5\) rolunu oynar. Fibonacci sayilari
$$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2}$$
icin indirgenmis us
$$e_n\equiv 5^{F_n}\pmod G$$
olarak tanimlanir. Eger
$$\beta^{e_n}=a_n+b_nu$$
seklinde yaziliyorsa, \(n\). terimin katkisi
$$s_n=b_n^5+(-a_n)^5\pmod p$$
olur. Istenen toplam
$$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p$$
degeridir. Dogrudan \(5^{F_n}\) uslerini hesaplamak imkansiza yakindir; cozum, bu dev usleri kisa bir moduler rekurrense indirip \(\beta\)'nin kuvvetlerini sabit bir cebir icinde takip eder.
Uc uygulama da ayni fikri kullanir: altin oranla baglantili \(\sqrt5-2\) tabanini, \(5^{F_n}\)'nin carpimsal davranisini ve sadece 64 elemanli bir ikili kuvvet tablosunu birlestirir.
\(R\) cebiri, \(u^2=5\) kosuluyla \(1,u\) tabaninda temsil edilir. Dolayisiyla carpim kuralı
$$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p$$
olur. Uygulamalar tam olarak bu formulu kullanir. Boylece \(\beta\)'nin her kuvveti yine \(a+bu\) biciminde kalir ve istenen terim iki katsayidan dogrudan okunur.
"Golden" nitelemesi gercektir. Eger
$$\phi=\frac{1+\sqrt5}{2}$$
altin oran ise \(\phi^3=2+\sqrt5\) olur; dolayisiyla
$$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$$
Ayrica
$$\left(u-2\right)\left(u+2\right)=u^2-4=1,$$
yani \(\beta\) cebirde tersinir bir elemandir.
Bu ozel asal icin \(p\equiv 4\pmod 5\) oldugundan ve \(5\equiv 1\pmod 4\) oldugu icin karesel karsililik ile \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\) bulunur. Demek ki \(u^2-5\), \(\mathbb{F}_p\) uzerinde ayrisir. Baska bir ifadeyle \(R\), \(\mathbb{F}_p\times\mathbb{F}_p\) ile izomorf olan ayrisan bir kuadratik cebirdir. Kod bu izomorfizmi acikca kullanmaz; \(1,u\) bazindaki katsayi temsili zaten yeterlidir.
Fibonacci bagintisi hemen sunu verir:
$$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$$
\(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\) oldugundan her birimin carpimsal periyodu \(p-1\)'i boler. Bu yuzden \(p-1\)'in her katı usler icin guvenli bir moduldur. Uygulamalar daha buyuk olan
$$G=p^2-1=(p-1)(p+1)$$
sayisini kullanir. Bu secim minimal degildir ama \(p-1\mid G\) oldugu icin tamamen dogrudur.
Boylece devasa \(5^{F_n}\) sayilarinin yerine sadece
$$e_n\equiv 5^{F_n}\pmod G$$
kalintilarini tutmak yeterli olur. Bu kalintilar da
$$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3)$$
rekurrensini saglar. Sorunun asil sadeleşmesi budur: Fibonacci indekslerindeki toplamsal buyume, tek bir moduler carpimla ilerleyen kisa bir us dizisine donusur.
Bu cebirde \(u\mapsto -u\) involusyonu vardir; yani
$$\overline{a+bu}=a-bu.$$
Buna karsilik gelen norm
$$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p$$
seklindedir. Taban eleman icin
$$N(\beta)=(u-2)(-u-2)=4-u^2=-1$$
elde edilir. Bütün \(e_n\) degerleri tektir: dizi \(5,5\) ile baslar ve cift olan \(G\) modunda tek kalintilarin carpimi yine tek kalir. Bu nedenle
$$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$$
Dolayisiyla
$$\beta^{e_n}=a_n+b_nu$$
ise her zaman
$$a_n^2-5b_n^2\equiv -1\pmod p$$
olur. Bu Pell-tipli kongruens nihai cevap degildir, ama tum katsayi ciftlerinin ayni cebirsel egride kaldigini gosterir ve guclu bir tutarlilik denetimi saglar.
\(\beta=u-2\) ile baslayip art arda carpinca
$$\beta^1=-2+u,$$
$$\beta^2=9-4u,$$
$$\beta^3=-38+17u,$$
$$\beta^4=161-72u,$$
$$\beta^5=-682+305u$$
elde edilir. En kucuk kontrol noktasi us \(1\) icindir:
$$s(1)=1^5+2^5=33.$$
Gercek toplam \(n=2\) ile, yani \(e_2=5\) iken baslar. Bu yuzden ilk biriken terim
$$s_2=305^5+682^5\equiv 257933744\pmod p$$
olur. Sonraki indirgenmis us
$$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G$$
ve \(\beta^{25}\) ayni bazda cozulunce
$$s_3\equiv 26500067\pmod p$$
elde edilir. Bunlar uygulamalardaki kucuk dogrulama degerleriyle aynidir. Daha sonra ayni rekurrens ve kuvvet alma deseni \(n=1{,}618{,}034\)'e kadar surer.
Her cebir elemani, \(a+bu\) ifadesini temsil eden \((a,b)\) kalinti cifti olarak saklanir. Carpim, yukaridaki formulle yapildigi icin tum islemler mod \(p\) altinda iki koordinatta kalir. \((-a)^5\) terimi, ilk koordinatin mod \(p\) altindaki toplamsal tersinin besinci kuvveti olarak hesaplanir.
C++, Python ve Java uygulamalari once
$$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$$
tablosunu ardışik kare alma ile olusturur. Bu yeterlidir, cunku secilen modulle her zaman \(0\le e_n<G<2^{64}\) vardir. Gerekli her \(\beta^{e_n}\) kuvveti daha sonra \(e_n\)'nin ikili acilimindan yeniden kurulur.
Uygulamalar hicbir zaman Fibonacci sayilarini acikca tutmaz. Yalnizca son iki us kalintisi saklanir; ikisi de baslangicta \(5\)'tir. Cevap \(n=2\) terimiyle baslatilir, sonra her \(n\ge 3\) icin
$$e_n\equiv e_{n-1}e_{n-2}\pmod G$$
hesaplanir, \(\beta^{e_n}\) ikili tablodan kurulur, \(a_n\) ve \(b_n\) okunur, \(b_n^5+(-a_n)^5\pmod p\) bulunur ve sonuca eklenir. Uc dildeki surumler sadece dusuk seviyeli moduler carpim ayrintilarinda farklidir; matematik aynidir.
\(M=1{,}618{,}034\) olsun. Ikili kuvvet tablosunu hazirlamak \(64\) cebir carpimi gerektirir. Sonraki her terim, us rekurrensi icin bir moduler carpim ve \(\beta^{e_n}\)'yi bitlerinden kurmak icin en fazla \(64\) cebir carpimi kullanir. Dolayisiyla calisma suresi
$$O(M\log G)$$
olur; \(\log G<64\) oldugu icin bu pratikte indeks sayisina gore dogrusala cok yakindir.
Bellek kullanimi \(O(1)\)'dir: sabit boyutlu kuvvet tablosu, iki guncel us, birikimli toplam ve birkac gecici cebir elemani yeterlidir.
Sean \(p=398874989\) y \(G=p^2-1\). Todo el calculo se hace dentro del algebra bidimensional
$$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$$
donde \(u\) desempena el papel de \(\sqrt5\). Para los numeros de Fibonacci
$$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2},$$
se define el exponente reducido
$$e_n\equiv 5^{F_n}\pmod G.$$
Si
$$\beta^{e_n}=a_n+b_nu,$$
entonces la contribucion del indice \(n\) es
$$s_n=b_n^5+(-a_n)^5\pmod p.$$
Hay que calcular
$$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p.$$
Construir de forma directa los exponentes \(5^{F_n}\) seria inviable. La solucion solo funciona porque esos exponentes enormes se reemplazan por una recurrencia modular corta, y porque las potencias de \(\beta\) siempre se manipulan dentro del algebra fija \(R\).
Las tres implementaciones explotan la misma estructura: el elemento base \(\sqrt5-2\), su relacion con la razon aurea, el comportamiento multiplicativo de \(5^{F_n}\) y una tabla binaria de solo 64 potencias.
El algebra \(R\) se representa en la base \(1,u\) con la relacion \(u^2=5\). Por tanto, la multiplicacion viene dada por
$$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p.$$
Esa es exactamente la regla que usan las implementaciones. Toda potencia de \(\beta\) sigue teniendo la forma \(a+bu\), de modo que el sumando final se obtiene leyendo solo dos coeficientes.
La palabra "golden" no es accidental. Si
$$\phi=\frac{1+\sqrt5}{2},$$
entonces \(\phi^3=2+\sqrt5\), y por eso
$$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$$
Ademas,
$$\left(u-2\right)\left(u+2\right)=u^2-4=1,$$
asi que \(\beta\) es una unidad del algebra.
Para este primo concreto se tiene \(p\equiv 4\pmod 5\). Como \(5\equiv 1\pmod 4\), la reciprocidad cuadratica da \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\). Eso significa que \(u^2-5\) se descompone ya sobre \(\mathbb{F}_p\), y por tanto \(R\) es un algebra cuadratica escindida, isomorfa a \(\mathbb{F}_p\times\mathbb{F}_p\). El codigo no necesita escribir ese isomorfismo; la base \(1,u\) es suficiente y mas comoda.
La recurrencia de Fibonacci implica inmediatamente
$$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$$
Como \(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\), toda unidad tiene periodo multiplicativo divisor de \(p-1\). Asi, cualquier multiplo de \(p-1\) sirve como modulo seguro para los exponentes. Las implementaciones usan la cantidad mayor
$$G=p^2-1=(p-1)(p+1),$$
que no es minima, pero sigue siendo correcta porque \(p-1\mid G\).
De este modo, el enorme numero \(5^{F_n}\) se sustituye por el residuo
$$e_n\equiv 5^{F_n}\pmod G.$$
Esos residuos satisfacen la recurrencia compacta
$$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3).$$
Esta es la simplificacion decisiva: en vez de seguir exponenciales gigantescas, el algoritmo avanza toda la parte de los exponentes con una sola multiplicacion modular por paso.
El algebra posee la involucion \(u\mapsto -u\), es decir,
$$\overline{a+bu}=a-bu.$$
La norma asociada es
$$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p.$$
Para el elemento base \(\beta=u-2\),
$$N(\beta)=(u-2)(-u-2)=4-u^2=-1.$$
Todos los \(e_n\) son impares: la sucesion empieza en \(5,5\) y, modulo el numero par \(G\), el producto de residuos impares sigue siendo impar. Por tanto,
$$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$$
En consecuencia, si
$$\beta^{e_n}=a_n+b_nu,$$
entonces siempre se cumple
$$a_n^2-5b_n^2\equiv -1\pmod p.$$
Esta congruencia de tipo Pell no es la respuesta final, pero describe con precision la forma de todos los pares de coeficientes y aporta una verificacion matematica muy util.
Partiendo de \(\beta=u-2\), la multiplicacion repetida produce
$$\beta^1=-2+u,$$
$$\beta^2=9-4u,$$
$$\beta^3=-38+17u,$$
$$\beta^4=161-72u,$$
$$\beta^5=-682+305u.$$
El punto de control mas pequeno es el exponente \(1\): como \(\beta^1=-2+u\), se obtiene
$$s(1)=1^5+2^5=33.$$
La suma real empieza en \(n=2\), donde \(e_2=5\). Por eso el primer termino acumulado es
$$s_2=305^5+682^5\equiv 257933744\pmod p.$$
El siguiente exponente reducido es
$$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G,$$
y al evaluar \(\beta^{25}\) en la misma base aparece
$$s_3\equiv 26500067\pmod p.$$
Esos son exactamente los pequenos puntos de control que tambien usan las implementaciones. A partir de ahi, el mismo patron de recurrencia y reconstruccion se repite hasta \(n=1{,}618{,}034\).
Cada elemento del algebra se guarda como un par de residuos \((a,b)\) que representa \(a+bu\). La multiplicacion usa la formula anterior, asi que toda la aritmetica permanece en dos coordenadas modulo \(p\). El termino \((-a)^5\) se obtiene tomando la quinta potencia, modulo \(p\), del inverso aditivo de la primera coordenada.
Las implementaciones en C++, Python y Java precalculan
$$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$$
mediante cuadrados sucesivos. Esa tabla basta porque con el modulo elegido siempre se cumple \(0\le e_n<G<2^{64}\). Cualquier potencia \(\beta^{e_n}\) se reconstruye luego a partir de los bits de \(e_n\).
En ningun momento se almacenan los propios numeros de Fibonacci. Solo se mantienen los dos residuos de exponente mas recientes, ambos inicializados en \(5\). La respuesta empieza con el termino \(n=2\), y para cada \(n\ge 3\) se calcula
$$e_n\equiv e_{n-1}e_{n-2}\pmod G,$$
se reconstruye \(\beta^{e_n}\) desde la tabla binaria, se extraen \(a_n\) y \(b_n\), se evalua \(b_n^5+(-a_n)^5\pmod p\) y se suma al acumulado. Los tres lenguajes difieren solo en detalles de implementacion de la aritmetica modular.
Sea \(M=1{,}618{,}034\). Preparar la tabla binaria cuesta \(64\) multiplicaciones en el algebra. Cada termino posterior requiere una multiplicacion modular para la recurrencia de exponentes y, como mucho, \(64\) multiplicaciones en el algebra para reconstruir \(\beta^{e_n}\) a partir de sus bits. Por tanto, el tiempo total es
$$O(M\log G),$$
y como \(\log G<64\), en la practica esto es esencialmente lineal en el numero de indices procesados.
La memoria es \(O(1)\): una tabla fija de potencias, dos exponentes corrientes, la suma acumulada y unos pocos elementos temporales del algebra.
设 \(p=398874989\)，并记 \(G=p^2-1\)。整道题的计算都放在二次代数
$$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$$
中进行，其中 \(u\) 扮演 \(\sqrt5\) 的角色。Fibonacci 数列满足
$$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2}.$$
定义约化后的指数
$$e_n\equiv 5^{F_n}\pmod G.$$
如果把
$$\beta^{e_n}=a_n+b_nu$$
写成基底 \(1,u\) 下的坐标形式，那么第 \(n\) 项贡献就是
$$s_n=b_n^5+(-a_n)^5\pmod p.$$
目标是求出
$$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p.$$
如果直接处理 \(5^{F_n}\)，指数会迅速膨胀到完全无法操作的规模。真正有效的做法，是把这些巨大指数压缩成一个很短的模递推，再在固定的二维代数 \(R\) 中计算 \(\beta\) 的幂。
三份实现使用的是同一套数学骨架：以 \(\sqrt5-2\) 这个“黄金”元素为底，利用 \(5^{F_n}\) 的乘法结构，把问题化成一个长度固定、位宽固定的幂运算流程。
代数 \(R\) 以 \(1,u\) 为基底，并满足 \(u^2=5\)。因此，任意两个元素相乘时都有明确的坐标公式
$$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p.$$
这正是实现里使用的乘法规则。于是 \(\beta\) 的任何幂都仍然可以写成 \(a+bu\) 的形式，题目最后要加的量也就只依赖这两个系数。
题目名称里的 “Golden” 不是装饰。若记黄金比例为
$$\phi=\frac{1+\sqrt5}{2},$$
则 \(\phi^3=2+\sqrt5\)，所以
$$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$$
另外，
$$\left(u-2\right)\left(u+2\right)=u^2-4=1,$$
这说明 \(\beta\) 在该代数中是可逆元。
对这个具体模数还有一层很重要的事实：\(p\equiv 4\pmod 5\)。又因为 \(5\equiv 1\pmod 4\)，由二次互反律可得 \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\)。也就是说，\(u^2-5\) 在 \(\mathbb{F}_p\) 上已经分裂，因此 \(R\) 其实是一个拆分二次代数，同构于 \(\mathbb{F}_p\times\mathbb{F}_p\)。代码并不需要显式写出这个同构；直接在基底 \(1,u\) 中做系数运算就足够了。
由 Fibonacci 递推立刻得到
$$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$$
而 \(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\)，所以任何可逆元的乘法周期都整除 \(p-1\)。因此，任何 \(p-1\) 的倍数都可以作为安全的指数模数。实现里选用的是更大的
$$G=p^2-1=(p-1)(p+1),$$
它不是最小周期，但因为 \(p-1\mid G\)，所以完全正确。
这一步把原本巨大的 \(5^{F_n}\) 压缩成模 \(G\) 的剩余类
$$e_n\equiv 5^{F_n}\pmod G.$$
这些剩余类满足极其紧凑的递推
$$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3).$$
这就是整道题最关键的化简：原来在 Fibonacci 指数上进行的巨大加法增长，被改写成每一步只需一次模乘的短递推。
在这个代数里有自然的共轭映射 \(u\mapsto -u\)，于是
$$\overline{a+bu}=a-bu.$$
对应的范数为
$$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p.$$
对基元 \(\beta=u-2\) 来说，
$$N(\beta)=(u-2)(-u-2)=4-u^2=-1.$$
所有 \(e_n\) 都是奇数：序列从 \(5,5\) 出发，而 \(G\) 是偶数，因此奇数剩余类相乘后仍保持奇性。于是
$$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$$
换句话说，只要
$$\beta^{e_n}=a_n+b_nu,$$
就一定满足
$$a_n^2-5b_n^2\equiv -1\pmod p.$$
这个 Pell 型同余并不是最终答案，但它刻画了所有系数对 \((a_n,b_n)\) 所在的代数曲线，也是实现正确性的一个天然检验。
从 \(\beta=u-2\) 出发，连续相乘可得
$$\beta^1=-2+u,$$
$$\beta^2=9-4u,$$
$$\beta^3=-38+17u,$$
$$\beta^4=161-72u,$$
$$\beta^5=-682+305u.$$
指数为 \(1\) 时有一个很小的检查点。因为 \(\beta^1=-2+u\)，所以
$$s(1)=1^5+2^5=33.$$
真正的求和从 \(n=2\) 开始，此时 \(e_2=5\)，因此第一个被累加的项为
$$s_2=305^5+682^5\equiv 257933744\pmod p.$$
下一步的约化指数是
$$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G,$$
再把 \(\beta^{25}\) 写回 \(a+bu\) 的形式，就得到
$$s_3\equiv 26500067\pmod p.$$
这些数值正好对应实现中的小规模校验点。之后的每一步都重复同样的“递推指数 + 二进制重建幂 + 读取系数”的模式，一直做到 \(n=1{,}618{,}034\)。
每个代数元素都用一个二元组 \((a,b)\) 表示，含义是 \(a+bu\)。乘法完全按照上面的坐标公式进行，因此所有运算都只是在模 \(p\) 的两个坐标上展开。\((-a)^5\) 则通过先取第一坐标的加法逆元，再做五次幂得到。
C++、Python 和 Java 实现都会先预处理
$$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$$
这 64 个幂，通过不断平方得到。之所以 64 项就够，是因为选定的指数模数满足 \(0\le e_n<G<2^{64}\)。因此，只要知道 \(e_n\) 的二进制展开，就能把 \(\beta^{e_n}\) 从这张表中重建出来。
实现从来不会显式保存 Fibonacci 数本身。它只保留最近两个指数剩余类，初值都是 \(5\)。答案先用 \(n=2\) 的那一项初始化；随后对每个 \(n\ge 3\) 计算
$$e_n\equiv e_{n-1}e_{n-2}\pmod G,$$
再根据二进制幂表重建 \(\beta^{e_n}\)，读出 \(a_n\) 和 \(b_n\)，求出 \(b_n^5+(-a_n)^5\pmod p\)，最后加到总和中。三种语言的底层模乘细节有所不同，但算法流程完全一致。
记 \(M=1{,}618{,}034\)。预处理二进制幂表需要 \(64\) 次代数乘法。之后的每一项需要一次指数递推的模乘，以及至多 \(64\) 次代数乘法来按位重建 \(\beta^{e_n}\)。因此总时间复杂度为
$$O(M\log G),$$
而由于 \(\log G<64\)，在这里可以把它看成关于 \(M\) 的近似线性时间。
空间复杂度是 \(O(1)\)：只需一个固定大小的幂表、两个当前指数、一个运行中的总和，以及少量临时代数元素。
Положим \(p=398874989\) и \(G=p^2-1\). Все вычисления ведутся в двумерной алгебре
$$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$$
где \(u\) играет роль \(\sqrt5\). Для чисел Фибоначчи
$$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2}$$
вводится сокращенный показатель
$$e_n\equiv 5^{F_n}\pmod G.$$
Если
$$\beta^{e_n}=a_n+b_nu,$$
то вклад индекса \(n\) равен
$$s_n=b_n^5+(-a_n)^5\pmod p.$$
Нужно вычислить
$$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p.$$
Прямая работа с числами \(5^{F_n}\) невозможна из-за их размера. Решение появляется только после того, как гигантские показатели заменяются короткой модульной рекурсией, а степени \(\beta\) считаются внутри фиксированной алгебры \(R\).
Все три реализации используют одну и ту же идею: золотой элемент \(\sqrt5-2\), мультипликативное поведение \(5^{F_n}\) и двоичную таблицу степеней из 64 элементов.
Алгебра \(R\) записывается в базисе \(1,u\) при условии \(u^2=5\). Поэтому произведение двух элементов имеет вид
$$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p.$$
Именно это правило и реализовано в коде. Каждая степень \(\beta\) снова имеет форму \(a+bu\), так что итоговое слагаемое получается простым чтением двух коэффициентов.
Связь с золотым сечением здесь буквальная. Если
$$\phi=\frac{1+\sqrt5}{2},$$
то \(\phi^3=2+\sqrt5\), следовательно
$$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$$
Кроме того,
$$\left(u-2\right)\left(u+2\right)=u^2-4=1,$$
значит, \(\beta\) является обратимым элементом алгебры.
Для данного простого числа выполняется \(p\equiv 4\pmod 5\). Так как \(5\equiv 1\pmod 4\), по закону квадратичной взаимности имеем \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\). Следовательно, \(u^2-5\) уже раскладывается над \(\mathbb{F}_p\), а сама алгебра \(R\) является расщепленной и изоморфна \(\mathbb{F}_p\times\mathbb{F}_p\). Программа не выписывает этот изоморфизм явно: координат \(1,u\) вполне достаточно.
Из рекурсии Фибоначчи сразу следует
$$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$$
Поскольку \(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\), период любой единицы делит \(p-1\). Значит, любой кратный \(p-1\) модуль подходит для сокращения показателей. Реализации выбирают более крупную величину
$$G=p^2-1=(p-1)(p+1),$$
которая не минимальна, но все равно корректна, потому что \(p-1\mid G\).
Это позволяет заменить огромный показатель \(5^{F_n}\) всего лишь остатком
$$e_n\equiv 5^{F_n}\pmod G.$$
Эти остатки удовлетворяют компактной рекурсии
$$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3).$$
Именно здесь происходит главное упрощение задачи: вместо отслеживания чудовищных экспонент достаточно одной модульной операции умножения на каждом шаге.
В алгебре есть естественная инволюция \(u\mapsto -u\), то есть
$$\overline{a+bu}=a-bu.$$
Ее норма равна
$$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p.$$
Для базового элемента \(\beta=u-2\) получаем
$$N(\beta)=(u-2)(-u-2)=4-u^2=-1.$$
Все числа \(e_n\) нечетны: последовательность стартует с \(5,5\), а по модулю четного числа \(G\) произведение нечетных остатков снова нечетно. Поэтому
$$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$$
Следовательно, если
$$\beta^{e_n}=a_n+b_nu,$$
то всегда выполнено
$$a_n^2-5b_n^2\equiv -1\pmod p.$$
Это конгруэнтное соотношение типа уравнения Пелля не является ответом само по себе, но оно точно описывает геометрию коэффициентов и дает сильную проверку корректности.
Начиная с \(\beta=u-2\), последовательные умножения дают
$$\beta^1=-2+u,$$
$$\beta^2=9-4u,$$
$$\beta^3=-38+17u,$$
$$\beta^4=161-72u,$$
$$\beta^5=-682+305u.$$
Самый маленький контрольный пример получается при показателе \(1\): поскольку \(\beta^1=-2+u\), имеем
$$s(1)=1^5+2^5=33.$$
Настоящее суммирование начинается с \(n=2\), то есть с \(e_2=5\). Поэтому первое накопленное слагаемое равно
$$s_2=305^5+682^5\equiv 257933744\pmod p.$$
Следующий сокращенный показатель равен
$$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G,$$
а вычисление \(\beta^{25}\) в том же базисе дает
$$s_3\equiv 26500067\pmod p.$$
Это в точности те малые контрольные значения, на которые опираются реализации. Дальше тот же шаблон “рекурсия по показателям + двоичное восстановление степени” продолжается до \(n=1{,}618{,}034\).
Каждый элемент алгебры хранится как пара остатков \((a,b)\), представляющая \(a+bu\). Умножение использует приведенную выше формулу, поэтому вся арифметика остается двумерной и ведется по модулю \(p\). Величина \((-a)^5\) получается как пятая степень аддитивной противоположности первого коэффициента.
Реализации на C++, Python и Java заранее вычисляют
$$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$$
последовательным возведением в квадрат. Этого достаточно, поскольку при выбранном модуле всегда выполняется \(0\le e_n<G<2^{64}\). Любая нужная степень \(\beta^{e_n}\) затем собирается по двоичной записи числа \(e_n\).
Ни одна из реализаций не хранит сами числа Фибоначчи. Поддерживаются только два последних остатка показателя, оба сначала равны \(5\). Ответ инициализируется слагаемым для \(n=2\), а далее для каждого \(n\ge 3\) вычисляется
$$e_n\equiv e_{n-1}e_{n-2}\pmod G,$$
после чего \(\beta^{e_n}\) восстанавливается из двоичной таблицы, извлекаются \(a_n\) и \(b_n\), считается \(b_n^5+(-a_n)^5\pmod p\), и результат добавляется к общей сумме. Языковые версии отличаются только низкоуровневыми деталями модульной арифметики.
Пусть \(M=1{,}618{,}034\). Построение двоичной таблицы требует \(64\) умножений в алгебре. Каждое следующее слагаемое использует одно модульное умножение для рекурсии по показателям и не более \(64\) умножений в алгебре для восстановления \(\beta^{e_n}\) по битам. Следовательно, время работы равно
$$O(M\log G),$$
а так как \(\log G<64\), на практике это почти линейная сложность по числу требуемых индексов.
Память имеет порядок \(O(1)\): таблица степеней постоянного размера, два текущих показателя, текущая сумма и несколько временных элементов алгебры.
لنضع \(p=398874989\) و\(G=p^2-1\). كل الحسابات تتم داخل الجبر ثنائي البعد
$$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$$
حيث يقوم \(u\) بدور \(\sqrt5\). ولأعداد فيبوناتشي
$$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2}$$
نعرّف الاس المختزل
$$e_n\equiv 5^{F_n}\pmod G.$$
واذا كتبنا
$$\beta^{e_n}=a_n+b_nu,$$
فان مساهمة الفهرس \(n\) هي
$$s_n=b_n^5+(-a_n)^5\pmod p.$$
المطلوب هو حساب
$$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p.$$
من المستحيل عمليًا التعامل مباشرة مع \(5^{F_n}\) بسبب ضخامة الاسس. الفكرة الناجحة هي ضغط هذه الاسس الهائلة في علاقة تكرارية معيارية قصيرة، ثم حساب قوى \(\beta\) داخل الجبر الثابت \(R\).
تستعمل التطبيقات الثلاثة الهيكل الرياضي نفسه: العنصر \(\sqrt5-2\) المرتبط بالنسبة الذهبية، والسلوك الضربي لـ \(5^{F_n}\)، وجدولًا ثنائيًا صغيرًا لا يتجاوز 64 قوة.
يمثل الجبر \(R\) على الاساس \(1,u\) مع العلاقة \(u^2=5\). لذلك يكون قانون الضرب
$$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p.$$
وهذا هو القانون نفسه الذي تستعمله التطبيقات. لذلك تبقى كل قوة من قوى \(\beta\) على الصورة \(a+bu\)، ويصبح الحد المطلوب في النهاية معتمدًا فقط على معاملين اثنين.
وصف المسألة بانها "ذهبية" له معنى حقيقي. اذا كانت
$$\phi=\frac{1+\sqrt5}{2}$$
هي النسبة الذهبية، فان \(\phi^3=2+\sqrt5\)، ومن ثم
$$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$$
كما ان
$$\left(u-2\right)\left(u+2\right)=u^2-4=1,$$
مما يعني ان \(\beta\) عنصر قابل للعكس في هذا الجبر.
وهناك حقيقة خاصة بهذا العدد الاولي: \(p\equiv 4\pmod 5\). وبما ان \(5\equiv 1\pmod 4\)، فان قانون التبادل التربيعي يعطي \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\). وهذا يعني ان \(u^2-5\) ينشطر بالفعل فوق \(\mathbb{F}_p\)، وبالتالي فالجبر \(R\) جبر تربيعي متشعب ومكافئ لـ \(\mathbb{F}_p\times\mathbb{F}_p\). لا يحتاج الكود إلى كتابة هذا التكافؤ صراحة؛ فالعمل المباشر على معاملات \(1,u\) يكفي تمامًا.
من علاقة فيبوناتشي نستنتج فورًا
$$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$$
ولأن \(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\)، فان الفترة الضربية لأي عنصر قابل للعكس تقسم \(p-1\). لذلك فكل مضاعف لـ \(p-1\) يصلح كمعيار آمن لاختزال الاسس. التطبيقات تختار القيمة الاكبر
$$G=p^2-1=(p-1)(p+1),$$
وهي ليست الاصغر، لكنها صحيحة تمامًا لأن \(p-1\mid G\).
بهذه الخطوة نستبدل العدد الهائل \(5^{F_n}\) بباقيه فقط:
$$e_n\equiv 5^{F_n}\pmod G.$$
وهذه البواقي تحقق العلاقة التكرارية المدمجة
$$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3).$$
وهنا يكمن التبسيط الحاسم: بدلًا من متابعة اسس خيالية الحجم، يكفي تنفيذ ضرب معياري واحد في كل خطوة.
في هذا الجبر يوجد تحويل مرافق طبيعي \(u\mapsto -u\)، ولذلك
$$\overline{a+bu}=a-bu.$$
والمعيار الموافق له هو
$$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p.$$
وبالنسبة إلى العنصر الاساسي \(\beta=u-2\) نحصل على
$$N(\beta)=(u-2)(-u-2)=4-u^2=-1.$$
جميع القيم \(e_n\) فردية: فالمتتالية تبدأ بـ \(5,5\)، ومعيار الاختزال \(G\) زوجي، وبالتالي يبقى حاصل ضرب البواقي الفردية فرديًا. لذا
$$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$$
ومن ثم اذا كتبنا
$$\beta^{e_n}=a_n+b_nu,$$
فلا بد ان يتحقق دائمًا
$$a_n^2-5b_n^2\equiv -1\pmod p.$$
هذا التطابق من نوع بيل ليس الجواب النهائي، لكنه يصف البنية الجبرية لكل زوج معاملات ويوفر فحصًا نظيفًا لصحة الحساب.
اذا بدأنا من \(\beta=u-2\)، فان الضرب المتكرر يعطي
$$\beta^1=-2+u,$$
$$\beta^2=9-4u,$$
$$\beta^3=-38+17u,$$
$$\beta^4=161-72u,$$
$$\beta^5=-682+305u.$$
اصغر نقطة تحقق تظهر عند الاس \(1\). بما ان \(\beta^1=-2+u\)، فان
$$s(1)=1^5+2^5=33.$$
لكن الجمع الحقيقي يبدأ من \(n=2\)، اي من \(e_2=5\). لذلك يكون اول حد متراكم
$$s_2=305^5+682^5\equiv 257933744\pmod p.$$
ثم يكون الاس المختزل التالي
$$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G,$$
وعند تقييم \(\beta^{25}\) بالطريقة نفسها نحصل على
$$s_3\equiv 26500067\pmod p.$$
وهذه هي قيم التحقق الصغيرة نفسها التي تعتمد عليها التطبيقات. وبعد ذلك يستمر النمط نفسه من تحديث الاسس ثم اعادة بناء القوة حتى \(n=1{,}618{,}034\).
يمثل كل عنصر في الجبر بزوج \((a,b)\) بمعنى \(a+bu\). ويستعمل الضرب الصيغة السابقة، لذلك تبقى كل العمليات داخل معاملين فقط بترديد \(p\). اما \((-a)^5\) فتحسب بأخذ المعكوس الجمعي للمعامل الاول ثم رفعه للقوة الخامسة.
تقوم تطبيقات C++ وPython وJava بتهيئة الجدول
$$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$$
عن طريق التربيع المتكرر. وهذا يكفي لأن الاس المختزل يحقق دائمًا \(0\le e_n<G<2^{64}\). وبعد ذلك يمكن اعادة بناء \(\beta^{e_n}\) مباشرة من التمثيل الثنائي للعدد \(e_n\).
لا تحتفظ التطبيقات نفسها بأعداد فيبوناتشي. بل تحتفظ فقط بآخر باقيين للاس، وكلاهما يبدأ بالقيمة \(5\). يهيأ الجواب بحد \(n=2\)، ثم لكل \(n\ge 3\) يحسب
$$e_n\equiv e_{n-1}e_{n-2}\pmod G,$$
ثم تعاد كتابة \(\beta^{e_n}\) انطلاقًا من جدول القوى الثنائية، وتستخرج \(a_n\) و\(b_n\)، وتحسب الكمية \(b_n^5+(-a_n)^5\pmod p\)، وتضاف إلى المجموع الجاري. الاختلاف بين اللغات الثلاث يقتصر على التفاصيل الدنيا للضرب المعياري.
اذا رمزنا إلى عدد الحدود بـ \(M=1{,}618{,}034\)، فان بناء جدول القوى الثنائية يحتاج إلى \(64\) عملية ضرب داخل الجبر. وكل حد تالٍ يحتاج إلى ضرب معياري واحد لعلاقة الاسس، ثم إلى ما لا يزيد على \(64\) عملية ضرب داخل الجبر لاعادة بناء \(\beta^{e_n}\) من بتاته. لذلك يكون الزمن الكلي
$$O(M\log G),$$
وبما ان \(\log G<64\)، فهذا يعني عمليًا زمنًا خطيًا تقريبًا بالنسبة إلى عدد الفهارس المطلوبة.
استهلاك الذاكرة هو \(O(1)\): جدول ثابت الحجم، واَسان حاليان، ومجموع جار، وعدة عناصر مؤقتة من الجبر.