We want the sum of all primes \(p \lt 10^8\) for which there exists an element \(g \in \mathbb{F}_p^{\times}\) that is both a primitive root modulo \(p\) and satisfies the Fibonacci-type recurrence
$$g^{n+2}\equiv g^{n+1}+g^n \pmod{p}.$$
Such an element is called a Fibonacci primitive root. A naive strategy would search through many primitive roots for every prime, but the recurrence collapses to one quadratic congruence, so each prime has at most two relevant candidates.
Because \(g\) is a primitive root modulo a prime, it is nonzero modulo \(p\). Dividing the recurrence by \(g^n\) gives
$$g^2\equiv g+1\pmod{p}.$$
Therefore a Fibonacci primitive root is exactly a primitive root that solves
$$x^2-x-1\equiv 0\pmod{p}.$$
This is the key simplification: instead of checking infinitely many recurrence steps, we only need to study one fixed polynomial.
The discriminant of \(x^2-x-1\) is
$$\Delta = 1+4 = 5.$$
For \(p\neq 5\), the quadratic has solutions if and only if \(5\) is a quadratic residue modulo \(p\), equivalently
$$\left(\frac{5}{p}\right)=1.$$
Since \(5\equiv 1\pmod 4\), quadratic reciprocity yields
$$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right),$$
so for odd primes \(p\neq 5\) the only possible residue classes are
$$p\equiv 1 \text{ or } 4 \pmod{5}.$$
This explains the early residue-class filter in the implementation. The small primes are exceptional: \(p=2\) and \(p=3\) give no solutions, while for \(p=5\) the polynomial becomes \((x-3)^2\), so \(3\) is the unique candidate and it is primitive modulo \(5\).
If \(s^2\equiv 5\pmod p\), then the inverse of \(2\) modulo an odd prime is
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
and the quadratic roots are
$$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p.$$
For \(p\neq 5\) there are exactly two such roots. Their sum is \(1\) and their product is \(-1\) modulo \(p\), but that algebraic relation does not guarantee primitiveness, so both candidates must still be tested.
The multiplicative group \(\mathbb{F}_p^{\times}\) is cyclic of order \(p-1\). An element is primitive if and only if its order is exactly \(p-1\). Write
$$p-1=\prod_{i=1}^{k} q_i^{e_i}$$
for the prime factorization of \(p-1\). Only the distinct prime divisors \(q_i\) are needed. The standard criterion is
$$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad \text{for every } i=1,\dots,k.$$
If even one of these powers is \(1\), then the order of \(g\) is a proper divisor of \(p-1\). If none is \(1\), the order cannot drop, so \(g\) is a primitive root.
The prime \(11\) passes the residue filter because \(11\equiv 1\pmod 5\). A square root of \(5\) modulo \(11\) is \(4\), since \(4^2=16\equiv 5\pmod{11}\). Therefore
$$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}.$$
Now \(11-1=10=2\cdot 5\). For \(g=8\), the primitive-root checks are
$$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}.$$
So \(8\) has order \(10\), hence it is a primitive root and \(11\) contributes to the final sum. This also shows that the residue test is only a necessary condition: it tells us when the quadratic has roots, not whether those roots generate the full group.
The C++, Python, and Java implementations all follow the same pipeline. They first build an odd-only smallest-prime-factor sieve. That single preprocessing step both identifies primes up to the limit and later factorizes \(p-1\) efficiently. The scan skips \(2\) and \(3\), adds \(5\) directly, and rejects all other primes with \(p\bmod 5\notin\{1,4\}\).
For the remaining primes, the implementation computes \(\sqrt{5}\pmod p\). When \(p\equiv 3\pmod 4\), a short exponentiation formula gives the square root immediately; otherwise it uses Tonelli-Shanks. From that square root it constructs the two roots \((1\pm \sqrt{5})/2\), extracts the distinct prime divisors of \(p-1\), and applies the primitive-root criterion. If either candidate passes, the prime is added to the running total.
Let \(N=10^8\). The odd-only sieve uses \(O(N)\) memory asymptotically, with roughly half the storage of a full sieve, and it is built in \(O(N\log\log N)\) time. After that, each surviving prime needs only a small number of modular exponentiations, one modular square-root computation, and factorization of \(p-1\) through the precomputed SPF table.
In practice the sieve and the prime scan dominate the runtime. The per-prime work stays modest because only two candidates are ever examined, and the primitive-root test uses only the distinct prime divisors of \(p-1\). This is dramatically faster than searching through all primitive roots or checking the Fibonacci recurrence term by term.
Gesucht ist die Summe aller Primzahlen \(p \lt 10^8\), für die es ein Element \(g \in \mathbb{F}_p^{\times}\) gibt, das zugleich eine Primitivwurzel modulo \(p\) ist und die Fibonacci-artige Rekursion
$$g^{n+2}\equiv g^{n+1}+g^n \pmod{p}$$
erfüllt. Ein solches \(g\) heißt Fibonacci-Primitivwurzel. Ein naiver Ansatz würde für jedes \(p\) viele Primitivwurzeln ausprobieren, doch die Rekursion kollabiert auf eine einzige quadratische Kongruenz. Dadurch bleiben pro Primzahl höchstens zwei Kandidaten übrig.
Da \(g\) als Primitivwurzel modulo einer Primzahl nicht null sein kann, dürfen wir durch \(g^n\) teilen und erhalten
$$g^2\equiv g+1\pmod{p}.$$
Damit ist eine Fibonacci-Primitivwurzel genau eine Primitivwurzel, die
$$x^2-x-1\equiv 0\pmod{p}$$
löst. Die Abhängigkeit von \(n\) verschwindet also vollständig; übrig bleibt nur eine feste quadratische Gleichung.
Die Diskriminante von \(x^2-x-1\) ist
$$\Delta = 1+4 = 5.$$
Für \(p\neq 5\) existieren Lösungen genau dann, wenn \(5\) quadratischer Rest modulo \(p\) ist, also
$$\left(\frac{5}{p}\right)=1.$$
Weil \(5\equiv 1\pmod 4\) gilt, liefert die quadratische Reziprozität
$$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right),$$
und damit kommen für ungerade Primzahlen \(p\neq 5\) nur die Restklassen
$$p\equiv 1 \text{ oder } 4 \pmod{5}$$
in Frage. Das erklärt den billigen Vorfilter in der Implementierung. Die kleinen Primzahlen sind Sonderfälle: Für \(p=2\) und \(p=3\) gibt es keine Lösung, während für \(p=5\) das Polynom zu \((x-3)^2\) wird; \(3\) ist dort der einzige Kandidat und zugleich primitive Wurzel.
Sei \(s^2\equiv 5\pmod p\). Dann ist für jede ungerade Primzahl das Inverse von \(2\) gegeben durch
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
und die beiden Nullstellen lauten
$$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p.$$
Für \(p\neq 5\) sind das genau zwei verschiedene Wurzeln. Ihre Summe ist \(1\), ihr Produkt ist \(-1\) modulo \(p\), aber daraus folgt noch nicht, dass eine von beiden die ganze multiplikative Gruppe erzeugt. Daher müssen beide explizit getestet werden.
Die multiplikative Gruppe \(\mathbb{F}_p^{\times}\) ist zyklisch und hat Ordnung \(p-1\). Ein Element ist genau dann primitive Wurzel, wenn seine Ordnung gleich \(p-1\) ist. Schreibe
$$p-1=\prod_{i=1}^{k} q_i^{e_i}$$
für die Primfaktorzerlegung von \(p-1\). Benötigt werden nur die verschiedenen Primteiler \(q_i\). Das Standardkriterium lautet
$$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad \text{für alle } i=1,\dots,k.$$
Sobald eine dieser Potenzen \(1\) ist, hat \(g\) nur eine echte Teilordnung von \(p-1\). Falls keine dieser Prüfungen fehlschlägt, muss die Ordnung genau \(p-1\) sein.
Die Primzahl \(11\) übersteht den Restklassenfilter, denn \(11\equiv 1\pmod 5\). Eine Quadratwurzel von \(5\) modulo \(11\) ist \(4\), weil \(4^2=16\equiv 5\pmod{11}\). Also gilt
$$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}.$$
Ferner ist \(11-1=10=2\cdot 5\). Für \(g=8\) prüft man
$$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}.$$
Also hat \(8\) Ordnung \(10\), ist damit primitive Wurzel und \(11\) trägt zur Summe bei. Das Beispiel zeigt auch, dass die Bedingung \(p\bmod 5\in\{1,4\}\) nur notwendig ist: Sie garantiert Nullstellen der quadratischen Kongruenz, aber noch keine Primitivwurzel.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst wird ein SPF-Sieb nur für ungerade Zahlen aufgebaut. Diese Vorverarbeitung liefert sowohl die Primzahlen bis zur Grenze als auch später eine schnelle Faktorisierung von \(p-1\). Danach werden \(2\) und \(3\) übersprungen, \(5\) direkt addiert und alle übrigen Primzahlen mit \(p\bmod 5\notin\{1,4\}\) sofort verworfen.
Für die verbleibenden Primzahlen berechnet die Implementierung \(\sqrt{5}\pmod p\). Wenn \(p\equiv 3\pmod 4\), genügt eine kurze Potenzformel; sonst kommt Tonelli-Shanks zum Einsatz. Aus der gefundenen Quadratwurzel entstehen die beiden Wurzeln \((1\pm \sqrt{5})/2\). Anschließend wird \(p-1\) in verschiedene Primteiler zerlegt und das Primitivwurzelkriterium angewandt. Besteht mindestens einer der beiden Kandidaten, wird \(p\) zur laufenden Summe addiert.
Mit \(N=10^8\) benötigt das ungerade SPF-Sieb asymptotisch \(O(N)\) Speicher, aber nur ungefähr die Hälfte einer vollständigen Tabelle, und seine Laufzeit ist \(O(N\log\log N)\). Danach braucht jede überlebende Primzahl nur wenige modulare Potenzierungen, eine modulare Quadratwurzel und die Faktorisierung von \(p-1\) über die vorberechnete SPF-Struktur.
In der Praxis dominieren das Sieb und der Primzahlscan die Laufzeit. Die Arbeit pro Primzahl bleibt klein, weil nie mehr als zwei Kandidaten geprüft werden und der Primitivwurzeltest nur die verschiedenen Primteiler von \(p-1\) verwendet. Das ist um Größenordnungen schneller als ein naives Durchprobieren aller Primitivwurzeln oder ein termweises Prüfen der Rekursion.
Toplanması istenen asallar, \(p \lt 10^8\) için öyle bir \(g \in \mathbb{F}_p^{\times}\) bulunanlardır ki \(g\) hem \(p\) modülünde bir primitif kök olsun hem de
$$g^{n+2}\equiv g^{n+1}+g^n \pmod{p}$$
Fibonacci-benzeri bağıntısını sağlasın. Böyle bir elemana Fibonacci primitif kökü denir. Saf kuvvetle arama yapmak her asal için çok sayıda primitif kökü denemeyi gerektirirdi; asıl fikir, bu bağıntının tek bir ikinci derece kongransa indirgenmesidir.
\(g\), asal modül altında primitif kök olduğundan sıfır olamaz. Bu yüzden bağıntıyı \(g^n\)'e bölüp
$$g^2\equiv g+1\pmod{p}$$
elde ederiz. Dolayısıyla aradığımız elemanlar tam olarak
$$x^2-x-1\equiv 0\pmod{p}$$
kongransını çözen primitif köklerdir. Böylece sonsuz gibi görünen tekrar koşulu tek bir polinom denetimine dönüşür.
\(x^2-x-1\) polinomunun diskriminantı
$$\Delta = 1+4 = 5$$
olduğundan, \(p\neq 5\) için çözüm bulunması ancak ve ancak \(5\)'in \(p\) modülünde karesel artık olmasıyla mümkündür:
$$\left(\frac{5}{p}\right)=1.$$
\(5\equiv 1\pmod 4\) olduğu için karesel karşılıklılık bize
$$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)$$
verir. Yani \(p\neq 5\) olan tek asal adaylar
$$p\equiv 1 \text{ veya } 4 \pmod{5}$$
sınıflarındadır. Uygulamadaki ucuz \(p\bmod 5\) filtresi tam olarak buradan gelir. Küçük asallar özel durumdur: \(p=2\) ve \(p=3\) için çözüm yoktur; \(p=5\) için ise polinom \((x-3)^2\) olur ve tek aday \(3\) zaten mod \(5\)'te primitif köktür.
Eğer \(s^2\equiv 5\pmod p\) ise, tek asal modüllerde \(2\)'nin tersi
$$2^{-1}\equiv \frac{p+1}{2}\pmod p$$
olur ve ikinci derece denklemin iki kökü
$$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p$$
şeklinde yazılır. \(p\neq 5\) için tam iki kök vardır. Bu köklerin toplamı \(1\), çarpımı \(-1\) mod \(p\)'dir; fakat bu cebirsel ilişki tek başına primitiflik garantisi vermez. Bu yüzden iki aday da ayrı ayrı sınanır.
\(\mathbb{F}_p^{\times}\) çarpma grubu çevrimseldir ve mertebesi \(p-1\)'dir. Bir eleman ancak mertebesi tam olarak \(p-1\) ise primitif köktür. Şunu yazalım:
$$p-1=\prod_{i=1}^{k} q_i^{e_i}.$$
Burada yalnızca farklı asal bölenler \(q_i\) gerekir. Standart test
$$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad (i=1,\dots,k)$$
şeklindedir. Bu kuvvetlerden biri \(1\) olursa, \(g\)'nin mertebesi \(p-1\)'in gerçek bir bölenine düşer. Hiçbiri \(1\) değilse, mertebe tam olarak \(p-1\)'dir.
\(11\), \(11\equiv 1\pmod 5\) olduğu için filtreyi geçer. Ayrıca \(4^2=16\equiv 5\pmod{11}\), dolayısıyla \(4\), \(5\)'in mod \(11\)'deki kareköklerinden biridir. Buradan
$$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}$$
elde edilir. Şimdi \(11-1=10=2\cdot 5\). \(g=8\) için testler
$$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}$$
olur. Demek ki \(8\)'in mertebesi \(10\)'dur; yani \(8\) primitif köktür ve \(11\) toplama dahil edilir. Bu örnek, \(p\bmod 5\) koşulunun yalnızca gerekli olduğunu da gösterir: ikinci derece kongransın kökleri vardır, ama bunların tüm grup için üreteç olması ayrı bir sınamadır.
C++, Python ve Java uygulamaları aynı hattı izler. Önce yalnızca tek sayıları tutan bir en küçük asal bölen tablosu kurulur. Bu ön işlem hem sınırın altındaki asalları üretir hem de daha sonra \(p-1\)'i hızlıca çarpanlara ayırmayı sağlar. Ardından \(2\) ve \(3\) atlanır, \(5\) doğrudan eklenir, geri kalan asallar içinde \(p\bmod 5\notin\{1,4\}\) olanlar hemen elenir.
Kalan asallar için uygulama \(\sqrt{5}\pmod p\) hesaplar. \(p\equiv 3\pmod 4\) ise kısa üs alma formülü yeterlidir; aksi durumda Tonelli-Shanks kullanılır. Bulunan karekökten \((1\pm \sqrt{5})/2\) adayları oluşturulur, \(p-1\)'in farklı asal bölenleri çıkarılır ve primitif kök testi uygulanır. İki adaydan biri başarılıysa ilgili asal toplamı artırır.
\(N=10^8\) için tek-sayı tabanlı SPF eleği asimptotik olarak \(O(N)\) bellek kullanır; tam eleğe göre yaklaşık yarı depolama ister ve \(O(N\log\log N)\) zamanda kurulur. Bundan sonra her uygun asal için yalnızca birkaç modüler üs alma, bir modüler karekök hesabı ve önceden hazırlanmış tablo üzerinden \(p-1\)'in çarpanlara ayrılması gerekir.
Pratikte zamanın büyük kısmı eleme ve asal taramasında gider. Asal başına iş yükü düşüktür; çünkü en fazla iki aday denenir ve primitif kök testi yalnızca \(p-1\)'in farklı asal bölenlerini kullanır. Bu yöntem, tüm primitif kökleri tek tek denemekten veya Fibonacci bağıntısını kuvvet kuvvet kontrol etmekten çok daha hızlıdır.
Debemos sumar todos los primos \(p \lt 10^8\) para los cuales existe un elemento \(g \in \mathbb{F}_p^{\times}\) que sea a la vez una raíz primitiva módulo \(p\) y satisfaga la recurrencia de tipo Fibonacci
$$g^{n+2}\equiv g^{n+1}+g^n \pmod{p}.$$
A ese elemento se le llama raíz primitiva de Fibonacci. Un enfoque ingenuo probaría muchas raíces primitivas para cada primo, pero la recurrencia se reduce a una sola congruencia cuadrática, así que cada primo deja como mucho dos candidatos reales.
Como \(g\) es una raíz primitiva módulo un primo, no puede ser cero módulo \(p\). Al dividir la recurrencia por \(g^n\) obtenemos
$$g^2\equiv g+1\pmod{p}.$$
Por tanto, una raíz primitiva de Fibonacci es exactamente una raíz primitiva que satisface
$$x^2-x-1\equiv 0\pmod{p}.$$
La dependencia en \(n\) desaparece por completo: ya no se estudia una sucesión infinita, sino un único polinomio.
El discriminante de \(x^2-x-1\) es
$$\Delta = 1+4 = 5.$$
Para \(p\neq 5\), la congruencia tiene soluciones si y solo si \(5\) es un residuo cuadrático módulo \(p\), es decir, si
$$\left(\frac{5}{p}\right)=1.$$
Como \(5\equiv 1\pmod 4\), la reciprocidad cuadrática da
$$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right),$$
de modo que para los primos impares \(p\neq 5\) solo sobreviven las clases
$$p\equiv 1 \text{ o } 4 \pmod{5}.$$
Ese es el motivo del filtro temprano por \(p\bmod 5\). Los primos pequeños son casos especiales: \(p=2\) y \(p=3\) no producen soluciones, mientras que para \(p=5\) el polinomio se convierte en \((x-3)^2\), así que \(3\) es el único candidato y además es raíz primitiva módulo \(5\).
Si \(s^2\equiv 5\pmod p\), entonces el inverso de \(2\) módulo un primo impar es
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
y las dos raíces del polinomio son
$$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p.$$
Para \(p\neq 5\) aparecen exactamente dos raíces. Su suma es \(1\) y su producto es \(-1\) módulo \(p\), pero esa relación algebraica no implica que una de ellas tenga orden \(p-1\); por eso ambas deben verificarse.
El grupo multiplicativo \(\mathbb{F}_p^{\times}\) es cíclico de orden \(p-1\). Un elemento es raíz primitiva si y solo si su orden es exactamente \(p-1\). Escribamos
$$p-1=\prod_{i=1}^{k} q_i^{e_i}.$$
Solo hacen falta los divisores primos distintos \(q_i\). El criterio estándar es
$$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad (i=1,\dots,k).$$
Si una sola de esas potencias vale \(1\), entonces el orden de \(g\) es un divisor propio de \(p-1\). Si ninguna vale \(1\), el orden no puede reducirse y \(g\) es primitivo.
El primo \(11\) pasa el filtro porque \(11\equiv 1\pmod 5\). Una raíz cuadrada de \(5\) módulo \(11\) es \(4\), ya que \(4^2=16\equiv 5\pmod{11}\). Por lo tanto,
$$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}.$$
Además, \(11-1=10=2\cdot 5\). Para \(g=8\), las pruebas son
$$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}.$$
Así, \(8\) tiene orden \(10\), es una raíz primitiva y \(11\) sí se suma. El ejemplo también deja claro que la condición de residuo cuadrático solo es necesaria: asegura raíces de la congruencia, pero no asegura que esas raíces generen todo el grupo.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero construyen una criba SPF solo para impares. Esa tabla de menor factor primo sirve tanto para enumerar los primos hasta el límite como para factorizar rápidamente \(p-1\) más adelante. Después se omiten \(2\) y \(3\), se agrega \(5\) directamente y se descartan de inmediato los demás primos con \(p\bmod 5\notin\{1,4\}\).
Para los primos restantes, la implementación calcula \(\sqrt{5}\pmod p\). Si \(p\equiv 3\pmod 4\), basta una exponenciación corta; en los demás casos se usa Tonelli-Shanks. A partir de esa raíz cuadrada se forman los dos candidatos \((1\pm \sqrt{5})/2\), se obtienen los divisores primos distintos de \(p-1\) y se aplica el criterio de raíz primitiva. Si cualquiera de los dos candidatos pasa la prueba, el primo se añade al total acumulado.
Con \(N=10^8\), la criba SPF para impares usa \(O(N)\) memoria en sentido asintótico, aunque con aproximadamente la mitad del almacenamiento de una criba completa, y se construye en \(O(N\log\log N)\) tiempo. Después, cada primo superviviente requiere pocas exponenciaciones modulares, una raíz cuadrada modular y la factorización de \(p-1\) usando la tabla SPF precalculada.
En la práctica dominan la criba y el recorrido de primos. El trabajo por primo es pequeño porque solo se examinan dos candidatos y la prueba de raíz primitiva utiliza únicamente los divisores primos distintos de \(p-1\). Eso hace que el método sea muchísimo más rápido que enumerar raíces primitivas o comprobar la recurrencia potencia por potencia.
我们要求的是所有满足下述条件的素数 \(p \lt 10^8\) 的和：存在某个 \(g \in \mathbb{F}_p^{\times}\)，它既是模 \(p\) 的原根，又满足 Fibonacci 型递推
$$g^{n+2}\equiv g^{n+1}+g^n \pmod{p}.$$
这样的 \(g\) 称为 Fibonacci 原根。直接做法会对每个素数尝试很多原根，但这里有一个关键化简：递推条件其实等价于一个固定的二次同余，所以每个素数最多只需要检查两个候选值。
由于 \(g\) 是素数模下的原根，所以 \(g\not\equiv 0\pmod p\)。把递推式两边同时除以 \(g^n\)，得到
$$g^2\equiv g+1\pmod{p}.$$
因此，所谓 Fibonacci 原根，等价于既是原根又满足
$$x^2-x-1\equiv 0\pmod{p}$$
的元素。这样一来，原本看似要检查很多项的递推，立刻变成了一个固定多项式的求根问题。
\(x^2-x-1\) 的判别式是
$$\Delta = 1+4 = 5.$$
对 \(p\neq 5\) 而言，这个二次同余有解，当且仅当 \(5\) 是模 \(p\) 的二次剩余，也就是
$$\left(\frac{5}{p}\right)=1.$$
因为 \(5\equiv 1\pmod 4\)，二次互反律给出
$$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right),$$
所以对奇素数 \(p\neq 5\)，只有
$$p\equiv 1 \text{ 或 } 4 \pmod{5}$$
才可能通过。这正是实现里先做 \(p\bmod 5\) 过滤的原因。小素数需要单独处理：\(p=2\) 和 \(p=3\) 时没有根；\(p=5\) 时多项式退化为 \((x-3)^2\)，唯一候选是 \(3\)，而 \(3\) 在模 \(5\) 下恰好也是原根。
若 \(s^2\equiv 5\pmod p\)，则在奇素数模下 \(2\) 的逆元为
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
于是二次同余的两个根就是
$$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p.$$
对 \(p\neq 5\) 来说，恰好有两个不同的根。它们的和是 \(1\)，乘积是 \(-1\) 模 \(p\)，但这种代数关系并不能直接推出哪一个一定是原根，因此两个候选都必须继续检验。
乘法群 \(\mathbb{F}_p^{\times}\) 是一个阶为 \(p-1\) 的循环群。元素 \(g\) 是原根，当且仅当它的阶正好等于 \(p-1\)。设
$$p-1=\prod_{i=1}^{k} q_i^{e_i}.$$
这里真正需要的只是不同的素因子 \(q_i\)。标准判定条件是
$$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad (i=1,\dots,k).$$
如果其中某一次幂等于 \(1\)，说明 \(g\) 的阶掉到了 \(p-1\) 的真因子；如果全部都不等于 \(1\)，那么它的阶就只能是 \(p-1\)。
\(11\equiv 1\pmod 5\)，所以 \(11\) 通过第一层过滤。因为 \(4^2=16\equiv 5\pmod{11}\)，所以 \(4\) 是模 \(11\) 下的一个 \(\sqrt{5}\)。于是
$$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}.$$
又因为 \(11-1=10=2\cdot 5\)，对 \(g=8\) 只需检查
$$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}.$$
所以 \(8\) 的阶就是 \(10\)，它是原根，因此 \(11\) 会被计入答案。这个例子也说明：二次剩余条件只保证二次同余有根，并不保证这些根自动成为整个乘法群的生成元。
C++、Python 和 Java 实现都遵循同一条流程。首先建立一个只覆盖奇数的最小素因子筛。这个预处理一方面用来枚举上界以内的素数，另一方面也让后续对 \(p-1\) 的分解变得很快。随后跳过 \(2\) 和 \(3\)，把 \(5\) 直接加入总和，并立即排除所有 \(p\bmod 5\notin\{1,4\}\) 的其他素数。
对剩余素数，实现会计算 \(\sqrt{5}\pmod p\)。当 \(p\equiv 3\pmod 4\) 时，可以用一条简短的幂公式直接得到平方根；其他情形则使用 Tonelli-Shanks。接着构造 \((1\pm \sqrt{5})/2\) 这两个候选，提取 \(p-1\) 的不同素因子，并应用原根判定。只要两个候选中有一个通过，该素数就被加入累加和。
设上界 \(N=10^8\)。奇数版 SPF 筛在渐近意义下占用 \(O(N)\) 空间，但常数约为完整筛的一半，构建时间为 \(O(N\log\log N)\)。之后，每个通过初筛的素数只需要少量模幂运算、一次模平方根计算，以及利用预处理表完成的 \(p-1\) 分解。
在实际运行中，主要耗时来自筛法和遍历素数。单个素数上的代价不高，因为最多只检查两个候选，而原根判定也只依赖 \(p-1\) 的不同素因子。与枚举所有原根或逐项验证 Fibonacci 递推相比，这个方法快得多。
Нужно просуммировать все простые \(p \lt 10^8\), для которых существует элемент \(g \in \mathbb{F}_p^{\times}\), одновременно являющийся первообразным корнем по модулю \(p\) и удовлетворяющий фибоначчиеподобному соотношению
$$g^{n+2}\equiv g^{n+1}+g^n \pmod{p}.$$
Такой элемент называют Fibonacci primitive root. Наивный перебор проверял бы много первообразных корней для каждого простого числа, но здесь рекуррентное условие сводится к одному квадратному сравнению, так что для каждого \(p\) остаются максимум два осмысленных кандидата.
Поскольку \(g\) является первообразным корнем по простому модулю, \(g\not\equiv 0\pmod p\). Делим исходное соотношение на \(g^n\) и получаем
$$g^2\equiv g+1\pmod{p}.$$
Следовательно, нам нужен первообразный корень, удовлетворяющий сравнению
$$x^2-x-1\equiv 0\pmod{p}.$$
Зависимость от \(n\) полностью исчезает: вместо проверки бесконечной на вид последовательности остаётся изучить один фиксированный многочлен.
Дискриминант многочлена \(x^2-x-1\) равен
$$\Delta = 1+4 = 5.$$
Для \(p\neq 5\) решения существуют тогда и только тогда, когда \(5\) является квадратичным вычетом по модулю \(p\), то есть
$$\left(\frac{5}{p}\right)=1.$$
Так как \(5\equiv 1\pmod 4\), из квадратичной взаимности следует
$$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right),$$
поэтому для нечётных простых \(p\neq 5\) возможны только классы
$$p\equiv 1 \text{ или } 4 \pmod{5}.$$
Именно этим объясняется ранний фильтр по \(p\bmod 5\) в реализации. Малые простые рассматриваются отдельно: для \(p=2\) и \(p=3\) решений нет, а при \(p=5\) многочлен превращается в \((x-3)^2\), так что единственный кандидат равен \(3\), и он действительно первообразный корень по модулю \(5\).
Пусть \(s^2\equiv 5\pmod p\). Тогда обратный к \(2\) элемент по нечётному простому модулю равен
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
и два корня квадратного сравнения имеют вид
$$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p.$$
Для \(p\neq 5\) это ровно два различных корня. Их сумма равна \(1\), а произведение равно \(-1\) по модулю \(p\), однако эта связь не даёт автоматически примитивность, поэтому проверять приходится оба значения.
Мультипликативная группа \(\mathbb{F}_p^{\times}\) циклична и имеет порядок \(p-1\). Элемент является первообразным корнем тогда и только тогда, когда его порядок равен ровно \(p-1\). Разложим
$$p-1=\prod_{i=1}^{k} q_i^{e_i}.$$
Нужны только различные простые делители \(q_i\). Стандартный тест таков:
$$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad (i=1,\dots,k).$$
Если хотя бы одна из этих степеней даёт \(1\), то порядок \(g\) является собственным делителем \(p-1\). Если ни одна проверка не проваливается, порядок обязан быть равен \(p-1\).
Простое число \(11\) проходит первый фильтр, потому что \(11\equiv 1\pmod 5\). Квадратный корень из \(5\) по модулю \(11\) равен \(4\), так как \(4^2=16\equiv 5\pmod{11}\). Поэтому
$$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}.$$
Далее \(11-1=10=2\cdot 5\). Для \(g=8\) проверяем
$$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}.$$
Значит, порядок \(8\) равен \(10\), то есть это первообразный корень, и \(11\) входит в итоговую сумму. Пример показывает и другое: условие на квадратичный вычет гарантирует существование корней квадратного сравнения, но не гарантирует, что эти корни порождают всю группу.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала строится SPF-решето только для нечётных чисел. Этот шаг одновременно перечисляет все простые до верхней границы и позволяет быстро факторизовать \(p-1\). Затем \(2\) и \(3\) пропускаются, \(5\) добавляется сразу, а все остальные простые с \(p\bmod 5\notin\{1,4\}\) отбрасываются без дополнительных вычислений.
Для оставшихся простых реализация вычисляет \(\sqrt{5}\pmod p\). Если \(p\equiv 3\pmod 4\), достаточно короткой формулы через возведение в степень; в остальных случаях используется алгоритм Тонелли-Шенкса. После этого строятся два кандидата \((1\pm \sqrt{5})/2\), извлекаются различные простые делители числа \(p-1\), и к обоим кандидатам применяется критерий первообразного корня. Если хотя бы один проходит проверку, соответствующее простое прибавляется к сумме.
При \(N=10^8\) нечётное SPF-решето использует \(O(N)\) памяти в асимптотическом смысле, но примерно вдвое меньше места, чем полная таблица, и строится за \(O(N\log\log N)\). После этого для каждого прошедшего фильтр простого требуется лишь несколько модульных возведений в степень, одно вычисление модульного квадратного корня и разложение числа \(p-1\) по заранее подготовленной таблице.
На практике основное время уходит на само решето и обход простых чисел. Работа на одно простое мала: проверяются только два кандидата, а тест примитивности использует лишь различные простые делители \(p-1\). Это на порядки быстрее, чем полный перебор первообразных корней или покомпонентная проверка рекуррентного соотношения.
نريد مجموع جميع الأعداد الأولية \(p \lt 10^8\) التي يوجد لها عنصر \(g \in \mathbb{F}_p^{\times}\) يكون في الوقت نفسه جذراً بدائياً بترديد \(p\) ويحقق علاقة من نمط فيبوناتشي:
$$g^{n+2}\equiv g^{n+1}+g^n \pmod{p}.$$
يسمى هذا العنصر جذراً بدائياً فيبوناتشياً. البحث الساذج كان سيفحص عدداً كبيراً من الجذور البدائية لكل أولي، لكن الفكرة الأساسية هنا هي أن العلاقة تختزل إلى مقارنة تربيعية واحدة، ولذلك لا يبقى لكل أولي إلا مرشحان على الأكثر.
بما أن \(g\) جذر بدائي modulo عدد أولي، فهو غير صفري modulo \(p\). بقسمة العلاقة على \(g^n\) نحصل على
$$g^2\equiv g+1\pmod{p}.$$
إذن الجذر البدائي الفيبوناتشي هو بالضبط جذر بدائي يحقق
$$x^2-x-1\equiv 0\pmod{p}.$$
وهذا يزيل الاعتماد على \(n\) تماماً: بدلاً من تتبع متتالية كاملة، نحل كثير حدود ثابتاً من الدرجة الثانية.
مميز كثير الحدود \(x^2-x-1\) هو
$$\Delta = 1+4 = 5.$$
لذلك، عندما \(p\neq 5\)، توجد حلول إذا وفقط إذا كان \(5\) بقايا تربيعية modulo \(p\)، أي
$$\left(\frac{5}{p}\right)=1.$$
وبما أن \(5\equiv 1\pmod 4\)، فإن قانون التبادلية التربيعية يعطي
$$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right),$$
ومن ثم فإن الأعداد الأولية الفردية الممكنة، مع استثناء \(5\)، هي فقط
$$p\equiv \pm 1 \pmod{5}.$$
وهذا يفسر مرشح البواقي السريع المستخدم قبل حساب أي جذر تربيعي معياري. أما الأعداد الصغيرة فلها معالجة خاصة: \(p=2\) و\(p=3\) لا يعطيان أي حل، بينما عند \(p=5\) يتحول كثير الحدود إلى \((x-3)^2\)، فيكون \(3\) المرشح الوحيد وهو بالفعل جذر بدائي modulo \(5\).
إذا كان \(s^2\equiv 5\pmod p\)، فإن معكوس \(2\) modulo أولي فردي هو
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
وعندها يكون جذرا المعادلة هما
$$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p.$$
عندما \(p\neq 5\) نحصل على جذرين مختلفين بالضبط. مجموعهما يساوي \(1\) وحاصل ضربهما يساوي \(-1\) modulo \(p\)، لكن هذه العلاقة الجبرية لا تكفي لإثبات أن أحدهما يولد المجموعة الضربية كلها، لذلك يجب اختبار المرشحين كليهما.
المجموعة الضربية \(\mathbb{F}_p^{\times}\) دورية ورتبتها \(p-1\). ويكون العنصر جذراً بدائياً إذا وفقط إذا كانت رتبته تساوي تماماً \(p-1\). اكتب
$$p-1=\prod_{i=1}^{k} q_i^{e_i}.$$
الذي نحتاجه فعلياً هو القواسم الأولية المميزة \(q_i\) فقط. المعيار القياسي هو
$$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad (i=1,\dots,k).$$
إذا ساوت إحدى هذه القوى \(1\)، فرتبة \(g\) تهبط إلى قاسم حقيقي لـ \(p-1\). وإذا لم يحدث ذلك لأي قاسم أولي مميز، فلابد أن رتبة \(g\) هي \(p-1\) نفسها.
العدد \(11\) يمر من مرشح البواقي لأن \(11\equiv 1\pmod 5\). كما أن \(4^2=16\equiv 5\pmod{11}\)، إذن \(4\) هو جذر تربيعي لـ \(5\) modulo \(11\). ومن ثم
$$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}.$$
ولدينا أيضاً \(11-1=10=2\cdot 5\). بالنسبة إلى \(g=8\)، تكون الاختبارات
$$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}.$$
إذن رتبة \(8\) هي \(10\)، أي أنه جذر بدائي، ولذلك يُضاف \(11\) إلى المجموع. ويبين هذا المثال أيضاً أن شرط البواقي التربيعية شرط لازم فقط: فهو يضمن وجود جذور للمعادلة التربيعية، لكنه لا يضمن أن تلك الجذور مولدات للمجموعة كلها.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولاً تُبنى بنية SPF للأعداد الفردية فقط، وهي تستخدم في الوقت نفسه لتوليد جميع الأعداد الأولية حتى الحد المطلوب، ثم لتفكيك \(p-1\) بسرعة لاحقاً. بعد ذلك تُتجاوز \(2\) و\(3\)، ويُضاف \(5\) مباشرة، وتُرفض فوراً جميع الأعداد الأولية الأخرى التي تحقق \(p\bmod 5\notin\{1,4\}\).
بعد ذلك تُحسب \(\sqrt{5}\pmod p\) لكل أولي باق. إذا كان \(p\equiv 3\pmod 4\)، تكفي صيغة قصيرة تعتمد على الأسس؛ وإلا يُستخدم Tonelli-Shanks. ثم تُبنى القيمتان \((1\pm \sqrt{5})/2\)، وتُستخرج القواسم الأولية المميزة للعدد \(p-1\)، ويُطبق معيار الجذر البدائي. إذا نجح أحد المرشحين، يُضاف ذلك الأولي إلى المجموع التراكمي.
عند \(N=10^8\)، يستخدم غربال SPF الخاص بالأعداد الفردية ذاكرة من رتبة \(O(N)\) من الناحية التقاربية، لكنه يستهلك تقريباً نصف مساحة الغربال الكامل، ويُبنى في زمن \(O(N\log\log N)\). بعد ذلك يحتاج كل أولي ناجٍ من المرشح الأولي إلى عدد صغير من عمليات الأس المعياري، وحساب جذر تربيعي معياري واحد، وتفكيك \(p-1\) بالاعتماد على جدول SPF الجاهز.
عملياً يهيمن الغربال ومسح الأعداد الأولية على زمن التنفيذ. أما الكلفة الخاصة بكل أولي فتبقى صغيرة لأن عدد المرشحين لا يتجاوز اثنين، ولأن اختبار الجذر البدائي يستخدم فقط القواسم الأولية المميزة لـ \(p-1\). وهذا أسرع بكثير من تعداد كل الجذور البدائية أو فحص علاقة فيبوناتشي حدّاً بعد حد.