Let \(M_q = 2^q - 1\), where \(q\) is the prime from the problem. The goal is to determine the canonical square root of \(q\) modulo the Mersenne number \(M_q\), and then report that enormous integer modulo \(10^9+7\).
A direct modular-square-root computation is hopeless because \(M_q\) itself has \(q\) binary digits. For the target value \(q = 74{,}207{,}281\), even writing down \(M_q\) is already infeasible. The implementations therefore avoid generic number-theoretic machinery and instead use a character sum whose binary digits are determined by quadratic residues modulo \(q\).
The central idea is that powers of 2 modulo a Mersenne number behave like roots of unity, so a classical quadratic Gauss sum turns into an explicit binary expansion of the desired square root.
Work modulo
\[ M_q = 2^q - 1. \]
Inside this ring we have \(2^q \equiv 1 \pmod{M_q}\), so exponents of 2 can always be reduced modulo \(q\). In other words, the element 2 plays the role of a nontrivial \(q\)-th root of unity.
Now define the quadratic character on the nonzero residue classes modulo \(q\):
\[ \chi(a)= \begin{cases} 1, & a \text{ is a nonzero quadratic residue mod } q, \\ -1, & a \text{ is a quadratic non-residue mod } q. \end{cases} \]
The sum used by the implementations is
\[ G=\sum_{a=1}^{q-1}\chi(a)\,2^a. \]
This is not an arbitrary weighted sum. It is the exact object that encodes the square root.
Expand the square of \(G\) modulo \(M_q\):
\[ G^2 = \sum_{a=1}^{q-1}\sum_{b=1}^{q-1}\chi(a)\chi(b)\,2^{a+b}. \]
For each fixed nonzero \(a\), write \(b \equiv at \pmod q\). Since \(\chi(ab)=\chi(a)\chi(b)=\chi(t)\) and exponents may be reduced modulo \(q\), this becomes
\[ G^2 \equiv \sum_{a=1}^{q-1}\sum_{t=1}^{q-1}\chi(t)\,2^{a(1+t)} \pmod{M_q}. \]
Now split into two cases.
If \(t \not\equiv -1 \pmod q\), then multiplication by \(1+t\) permutes the nonzero residue classes modulo \(q\), so
\[ \sum_{a=1}^{q-1}2^{a(1+t)} \equiv \sum_{u=1}^{q-1}2^u = 2^q-2 = M_q-1 \equiv -1 \pmod{M_q}. \]
If \(t \equiv -1 \pmod q\), then every exponent is \(0\) modulo \(q\), so the inner sum is simply \(q-1\).
Therefore
\[ G^2 \equiv \chi(-1)(q-1) - \sum_{t \ne -1}\chi(t) \pmod{M_q}. \]
Because the quadratic character has equally many \(+1\) and \(-1\) values,
\[ \sum_{t=1}^{q-1}\chi(t)=0, \]
so \(\sum_{t \ne -1}\chi(t) = -\chi(-1)\). Substituting gives the standard Gauss-sum identity
\[ G^2 \equiv \chi(-1)\,q = (-1)^{(q-1)/2}q \pmod{M_q}. \]
For the prime used here, \(q \equiv 1 \pmod 4\), hence \(\chi(-1)=1\) and
\[ G^2 \equiv q \pmod{M_q}. \]
So \(G\) is one of the two square roots of \(q\) modulo \(M_q\).
Let
\[ R=\sum_{\chi(a)=1}2^a, \qquad N=\sum_{\chi(a)=-1}2^a. \]
Then \(G = R - N\), while
\[ R+N=\sum_{a=1}^{q-1}2^a = M_q - 1. \]
Hence
\[ G = M_q - 1 - 2N, \qquad M_q - G = 1 + 2N. \]
So once the non-residue sum \(N\) is known, the opposite square root is available for free.
The remaining question is: which of \(G\) and \(M_q-G\) is the smaller positive root? The answer depends on \(q \bmod 8\).
The top bit \(2^{q-1}\) always appears in \(G\) with positive sign because
\[ \chi(q-1)=\chi(-1)=1. \]
The next bit \(2^{q-2}\) has sign \(\chi(q-2)=\chi(-2)=\chi(2)\), and the supplementary law gives
\[ \chi(2)=(-1)^{(q^2-1)/8} = \begin{cases} 1, & q \equiv 1 \pmod 8, \\ -1, & q \equiv 5 \pmod 8. \end{cases} \]
If \(q \equiv 1 \pmod 8\), then even in the most pessimistic case for the lower bits,
\[ G \ge 2^{q-1}+2^{q-2}-(2^{q-2}-2)=2^{q-1}+2, \]
so \(G > M_q/2\). Therefore the smaller root is
\[ M_q-G = 1+2N. \]
If \(q \equiv 5 \pmod 8\), then even giving every lower bit the favorable sign,
\[ G \le 2^{q-1}-2^{q-2}+(2^{q-2}-2)=2^{q-1}-2, \]
so \(G < M_q/2\). In that case \(G\) itself is the smaller root.
For \(q=5\), the nonzero quadratic residues are \(\{1,4\}\) and the non-residues are \(\{2,3\}\). Therefore
\[ G = 2^1 - 2^2 - 2^3 + 2^4 = 2 - 4 - 8 + 16 = 6. \]
Since \(M_5 = 31\), we get
\[ 6^2 = 36 \equiv 5 \pmod{31}. \]
Also \(5 \equiv 5 \pmod 8\), so the smaller root is exactly \(G=6\).
For \(q=17\), the same construction yields \(G=83{,}502\). The opposite root is
\[ M_{17}-G = 2^{17}-1-83{,}502 = 47{,}569. \]
Because \(17 \equiv 1 \pmod 8\), the smaller root is \(47{,}569\), and indeed
\[ 47{,}569^2 \equiv 17 \pmod{131{,}071}. \]
The implementation first builds a boolean table for the nonzero quadratic residues modulo \(q\). It only needs to iterate \(x=1,2,\dots,(q-1)/2\), because \(x^2 \equiv (-x)^2 \pmod q\), so these values already cover every nonzero residue exactly once.
Instead of recomputing each square from scratch, it maintains the invariant
\[ (x+1)^2 \equiv x^2 + (2x+1) \pmod q. \]
Since \(2x+1 \le q\) throughout that loop, each update needs at most one subtraction by \(q\). That is why the residue-generation phase is a tight \(O(q)\) scan with very small constant factors.
Next, the implementation sweeps through \(n=1,2,\dots,q-1\). At each step it updates the current power \(2^n \bmod 10^9+7\) by a single doubling.
If \(n\) is marked as a quadratic residue, that power is added to the running value of \(G\). If \(n\) is a non-residue, the same power is subtracted from \(G\) and added to the running value of \(N\). So the whole mathematical formula is evaluated in one pass, with only modular additions and subtractions.
Crucially, the code never constructs \(M_q\) and never performs a square-root routine modulo a gigantic number. It only evaluates the explicit binary expansion of the root and reduces the result modulo \(10^9+7\) as it goes.
After the sweep finishes, the implementation has exactly the two quantities needed for the final decision: \(G\) and \(N\), both already reduced modulo \(10^9+7\).
If \(q \equiv 1 \pmod 8\), the smaller root is \(1+2N\), so that value is returned. Otherwise the smaller root is \(G\), so the implementation returns the signed Gauss sum directly. The C++, Python, and Java versions all follow this same logic.
The algorithm performs two linear scans of length \(q-1\): one to mark quadratic residues, and one to accumulate the weighted powers of 2. Therefore the running time is \(O(q)\).
The memory usage is \(O(q)\) for the residue table. Aside from that table, the algorithm stores only a few modular accumulators and loop counters. This is exactly the right trade-off for the target prime: a byte-level table of length \(q\) is practical, while any attempt to represent \(M_q\) itself would be astronomically out of reach.
Sei \(M_q = 2^q - 1\), wobei \(q\) die in der Aufgabe vorgegebene Primzahl ist. Gesucht ist die kanonische Quadratwurzel von \(q\) modulo der Mersenne-Zahl \(M_q\), und anschließend soll dieser riesige Wert modulo \(10^9+7\) ausgegeben werden.
Ein direkter Quadratwurzel-Algorithmus modulo \(M_q\) ist aussichtslos, denn \(M_q\) besitzt selbst schon \(q\) Binärstellen. Für den Zielwert \(q = 74{,}207{,}281\) ist sogar das explizite Ausschreiben von \(M_q\) unmöglich. Deshalb nutzt die Lösung keine allgemeine Black-Box-Methode, sondern eine Charaktersumme, deren Binärdarstellung durch die quadratischen Reste modulo \(q\) festgelegt wird.
Die Grundidee ist, dass Potenzen von 2 modulo einer Mersenne-Zahl wie Einheitswurzeln wirken. Dadurch wird eine klassische quadratische Gaußsumme zu einer expliziten Binärentwicklung der gesuchten Quadratwurzel.
Gearbeitet wird modulo
\[ M_q = 2^q - 1. \]
In diesem Restklassenring gilt \(2^q \equiv 1 \pmod{M_q}\). Exponenten von 2 dürfen also stets modulo \(q\) reduziert werden. Anders gesagt: Die Zahl 2 verhält sich wie eine nichttriviale \(q\)-te Einheitswurzel.
Nun definieren wir den quadratischen Charakter auf den von 0 verschiedenen Restklassen modulo \(q\):
\[ \chi(a)= \begin{cases} 1, & a \text{ ist ein nichtverschwindender quadratischer Rest mod } q, \\ -1, & a \text{ ist ein quadratischer Nichtrest mod } q. \end{cases} \]
Die zentrale Summe lautet dann
\[ G=\sum_{a=1}^{q-1}\chi(a)\,2^a. \]
Genau diese Summe wird von den Implementierungen ausgewertet, denn sie kodiert die gesuchte Wurzel direkt.
Wir quadrieren \(G\) modulo \(M_q\):
\[ G^2 = \sum_{a=1}^{q-1}\sum_{b=1}^{q-1}\chi(a)\chi(b)\,2^{a+b}. \]
Für festes \(a \ne 0\) schreiben wir \(b \equiv at \pmod q\). Da \(\chi(ab)=\chi(a)\chi(b)=\chi(t)\) und Exponenten modulo \(q\) reduziert werden dürfen, erhalten wir
\[ G^2 \equiv \sum_{a=1}^{q-1}\sum_{t=1}^{q-1}\chi(t)\,2^{a(1+t)} \pmod{M_q}. \]
Nun kommen zwei Fälle vor.
Falls \(t \not\equiv -1 \pmod q\), dann permutiert die Multiplikation mit \(1+t\) die nichtnull Restklassen, also
\[ \sum_{a=1}^{q-1}2^{a(1+t)} \equiv \sum_{u=1}^{q-1}2^u = 2^q-2 = M_q-1 \equiv -1 \pmod{M_q}. \]
Falls \(t \equiv -1 \pmod q\), wird jeder Exponent zu \(0\) modulo \(q\), und die innere Summe ist einfach \(q-1\).
Daraus folgt
\[ G^2 \equiv \chi(-1)(q-1) - \sum_{t \ne -1}\chi(t) \pmod{M_q}. \]
Da der quadratische Charakter gleich viele \(+1\)- wie \(-1\)-Werte besitzt, gilt
\[ \sum_{t=1}^{q-1}\chi(t)=0. \]
Also ist \(\sum_{t \ne -1}\chi(t) = -\chi(-1)\), und wir erhalten die Gaußsummen-Identität
\[ G^2 \equiv \chi(-1)\,q = (-1)^{(q-1)/2}q \pmod{M_q}. \]
Für die hier relevante Primzahl gilt \(q \equiv 1 \pmod 4\), also \(\chi(-1)=1\) und damit
\[ G^2 \equiv q \pmod{M_q}. \]
Damit ist \(G\) eine der beiden Quadratwurzeln von \(q\) modulo \(M_q\).
Setze
\[ R=\sum_{\chi(a)=1}2^a, \qquad N=\sum_{\chi(a)=-1}2^a. \]
Dann gilt \(G = R - N\) und zugleich
\[ R+N=\sum_{a=1}^{q-1}2^a = M_q - 1. \]
Also
\[ G = M_q - 1 - 2N, \qquad M_q - G = 1 + 2N. \]
Sobald \(N\) bekannt ist, steht also auch die entgegengesetzte Wurzel ohne zusätzliche Arbeit fest.
Welche von \(G\) und \(M_q-G\) die kleinere positive Wurzel ist, entscheidet \(q \bmod 8\).
Das höchste Bit \(2^{q-1}\) tritt in \(G\) stets positiv auf, denn
\[ \chi(q-1)=\chi(-1)=1. \]
Das nächsthöchste Bit \(2^{q-2}\) hat Vorzeichen \(\chi(q-2)=\chi(-2)=\chi(2)\), und das Ergänzungsgesetz liefert
\[ \chi(2)=(-1)^{(q^2-1)/8} = \begin{cases} 1, & q \equiv 1 \pmod 8, \\ -1, & q \equiv 5 \pmod 8. \end{cases} \]
Für \(q \equiv 1 \pmod 8\) gilt selbst im ungünstigsten Fall für alle tieferen Bits
\[ G \ge 2^{q-1}+2^{q-2}-(2^{q-2}-2)=2^{q-1}+2, \]
also \(G > M_q/2\). Dann ist die kleinere Wurzel
\[ M_q-G = 1+2N. \]
Für \(q \equiv 5 \pmod 8\) erhält man dagegen selbst mit maximal günstigen tieferen Bits
\[ G \le 2^{q-1}-2^{q-2}+(2^{q-2}-2)=2^{q-1}-2, \]
also \(G < M_q/2\). Dann ist \(G\) selbst die kleinere Wurzel.
Für \(q=5\) sind die nichtnull quadratischen Reste \(\{1,4\}\), die Nichtreste sind \(\{2,3\}\). Damit
\[ G = 2^1 - 2^2 - 2^3 + 2^4 = 2 - 4 - 8 + 16 = 6. \]
Da \(M_5 = 31\), folgt
\[ 6^2 = 36 \equiv 5 \pmod{31}. \]
Außerdem gilt \(5 \equiv 5 \pmod 8\), also ist die kleinere Wurzel genau \(G=6\).
Für \(q=17\) liefert dieselbe Konstruktion \(G=83{,}502\). Die entgegengesetzte Wurzel ist
\[ M_{17}-G = 2^{17}-1-83{,}502 = 47{,}569. \]
Wegen \(17 \equiv 1 \pmod 8\) ist diesmal \(47{,}569\) die kleinere Wurzel, und tatsächlich gilt
\[ 47{,}569^2 \equiv 17 \pmod{131{,}071}. \]
Die Implementierung erzeugt zuerst eine Boolesche Tabelle der nichtnull quadratischen Reste modulo \(q\). Dazu genügt die Iteration über \(x=1,2,\dots,(q-1)/2\), denn \(x^2 \equiv (-x)^2 \pmod q\), also treten alle nichtnull Reste bereits genau einmal auf.
Statt jede Quadratzahl neu auszurechnen, wird die Invariante
\[ (x+1)^2 \equiv x^2 + (2x+1) \pmod q \]
verwendet. Da in dieser Schleife stets \(2x+1 \le q\) gilt, reicht pro Schritt höchstens eine Subtraktion von \(q\). Genau deshalb ist diese Phase ein sehr effizienter \(O(q)\)-Durchlauf.
Anschließend läuft die Implementierung einmal durch \(n=1,2,\dots,q-1\) und aktualisiert die aktuelle Potenz \(2^n \bmod 10^9+7\) jeweils durch eine Verdopplung.
Ist \(n\) ein quadratischer Rest, wird diese Potenz zum laufenden Wert von \(G\) addiert. Ist \(n\) ein Nichtrest, wird dieselbe Potenz von \(G\) subtrahiert und gleichzeitig zu \(N\) addiert. Auf diese Weise wird die gesamte Formel in einem einzigen linearen Durchlauf ausgewertet.
Entscheidend ist: Weder \(M_q\) noch eine allgemeine Quadratwurzel modulo einer riesigen Zahl werden jemals aufgebaut. Die Implementierung berechnet direkt die explizite Binärdarstellung der Wurzel und reduziert sie fortlaufend modulo \(10^9+7\).
Nach dem Durchlauf liegen genau die beiden benötigten Größen vor: \(G\) und \(N\), beide bereits modulo \(10^9+7\).
Falls \(q \equiv 1 \pmod 8\), ist die kleinere Wurzel \(1+2N\), und genau dieser Wert wird zurückgegeben. Andernfalls ist \(G\) bereits die kleinere Wurzel. Die C++-, Python- und Java-Implementierungen setzen diese mathematische Entscheidung identisch um.
Der Algorithmus benötigt zwei lineare Durchläufe der Länge \(q-1\): einen zum Markieren der quadratischen Reste und einen zum Aufsummieren der gewichteten Zweierpotenzen. Die Laufzeit ist also \(O(q)\).
Der Speicherverbrauch ist \(O(q)\) für die Resttabelle. Abgesehen davon werden nur einige modulare Akkumulatoren und Schleifenzähler gespeichert. Für die Zielprimzahl ist genau das die passende Strategie: Eine Byte-Tabelle der Länge \(q\) ist praktikabel, ein explizites Objekt der Größe \(2^q-1\) hingegen völlig unerreichbar.
\(M_q = 2^q - 1\) olsun; burada \(q\), soruda verilen asaldır. İstenen şey, \(q\)'nun Mersenne sayısı \(M_q\) modundaki kanonik karekökünü bulmak ve sonra bu devasa sayıyı \(10^9+7\) modunda raporlamaktır.
\(M_q\) üzerinde doğrudan bir modüler karekök algoritması kullanmak mümkün değildir; çünkü \(M_q\)'nun kendisi bile \(q\) bit uzunluğundadır. Hedef değer \(q = 74{,}207{,}281\) için \(M_q\)'yu açıkça yazmak bile imkansızdır. Bu yüzden çözüm, genel amaçlı bir yöntem yerine, bitleri \(q\) modundaki karesel kalıntılar tarafından belirlenen bir karakter toplamını kullanır.
Ana fikir şudur: Bir Mersenne modülünde 2'nin kuvvetleri birim kökler gibi davranır. Böylece klasik bir ikinci dereceden Gauss toplamı, aranan karekökün açık bir ikili açılımına dönüşür.
Şu mod altında çalışıyoruz:
\[ M_q = 2^q - 1. \]
Bu halkada \(2^q \equiv 1 \pmod{M_q}\) olduğu için, 2'nin üsleri her zaman \(q\) modunda indirgenebilir. Başka bir deyişle 2, burada önemsiz olmayan bir \(q\). dereceden birim kök rolü oynar.
Şimdi \(q\) modundaki sıfır olmayan artık sınıfları üzerinde karesel karakteri tanımlayalım:
\[ \chi(a)= \begin{cases} 1, & a \text{ sıfır olmayan bir karesel kalıntıysa}, \\ -1, & a \text{ karesel kalıntı değilse}. \end{cases} \]
Uygulamaların hesapladığı temel toplam
\[ G=\sum_{a=1}^{q-1}\chi(a)\,2^a \]
şeklindedir. Bu, rastgele bir ağırlıklı toplam değil; karekökü doğrudan veren nesnenin kendisidir.
\(G\)'nin karesini \(M_q\) modunda açalım:
\[ G^2 = \sum_{a=1}^{q-1}\sum_{b=1}^{q-1}\chi(a)\chi(b)\,2^{a+b}. \]
Her sabit \(a \ne 0\) için \(b \equiv at \pmod q\) yazalım. \(\chi(ab)=\chi(a)\chi(b)=\chi(t)\) olduğu ve üsler \(q\) modunda indirgenebildiği için
\[ G^2 \equiv \sum_{a=1}^{q-1}\sum_{t=1}^{q-1}\chi(t)\,2^{a(1+t)} \pmod{M_q} \]
elde edilir.
Burada iki durum vardır.
Eğer \(t \not\equiv -1 \pmod q\) ise, \(1+t\) ile çarpma sıfır olmayan artık sınıfları permüte eder. Dolayısıyla
\[ \sum_{a=1}^{q-1}2^{a(1+t)} \equiv \sum_{u=1}^{q-1}2^u = 2^q-2 = M_q-1 \equiv -1 \pmod{M_q}. \]
Eğer \(t \equiv -1 \pmod q\) ise her üs \(q\) modunda 0 olur; iç toplam bu kez sadece \(q-1\)'dir.
Böylece
\[ G^2 \equiv \chi(-1)(q-1) - \sum_{t \ne -1}\chi(t) \pmod{M_q}. \]
Karesel karakterin \(+1\) ve \(-1\) değerleri eşit sayıda olduğundan
\[ \sum_{t=1}^{q-1}\chi(t)=0 \]
olur. Buradan \(\sum_{t \ne -1}\chi(t) = -\chi(-1)\) gelir ve klasik özdeşlik ortaya çıkar:
\[ G^2 \equiv \chi(-1)\,q = (-1)^{(q-1)/2}q \pmod{M_q}. \]
Bu problemde kullanılan asal için \(q \equiv 1 \pmod 4\) olduğundan \(\chi(-1)=1\) ve sonuç
\[ G^2 \equiv q \pmod{M_q} \]
olur. Yani \(G\), \(q\)'nun \(M_q\) modundaki iki karekökünden biridir.
Şimdi
\[ R=\sum_{\chi(a)=1}2^a, \qquad N=\sum_{\chi(a)=-1}2^a \]
tanımlarını yapalım. O zaman \(G = R - N\) ve ayrıca
\[ R+N=\sum_{a=1}^{q-1}2^a = M_q - 1 \]
olduğu için
\[ G = M_q - 1 - 2N, \qquad M_q - G = 1 + 2N \]
elde edilir. Demek ki kalıntı olmayanlar toplamı \(N\) bilindiğinde, karşıt kök zaten bedavadan elde edilmiş olur.
Geriye şu kalır: Küçük pozitif kök hangisidir, \(G\) mi yoksa \(M_q-G\) mi? Bunu \(q \bmod 8\) belirler.
En yüksek bit \(2^{q-1}\),
\[ \chi(q-1)=\chi(-1)=1 \]
olduğu için \(G\)'de her zaman pozitif işaretle bulunur. Sonraki bit \(2^{q-2}\)'nin işareti ise \(\chi(q-2)=\chi(-2)=\chi(2)\)'dir ve yardımcı yasa şunu verir:
\[ \chi(2)=(-1)^{(q^2-1)/8} = \begin{cases} 1, & q \equiv 1 \pmod 8, \\ -1, & q \equiv 5 \pmod 8. \end{cases} \]
Eğer \(q \equiv 1 \pmod 8\) ise, alt bitlerin en kötü etkisinde bile
\[ G \ge 2^{q-1}+2^{q-2}-(2^{q-2}-2)=2^{q-1}+2 \]
olur; dolayısıyla \(G > M_q/2\). Bu durumda küçük kök
\[ M_q-G = 1+2N \]
olur.
Eğer \(q \equiv 5 \pmod 8\) ise, alt bitlere olabilecek en olumlu işaretleri verseniz bile
\[ G \le 2^{q-1}-2^{q-2}+(2^{q-2}-2)=2^{q-1}-2 \]
elde edilir; yani \(G < M_q/2\). O halde küçük kök doğrudan \(G\)'dir.
\(q=5\) için sıfır olmayan karesel kalıntılar \(\{1,4\}\), karesel kalıntı olmayanlar ise \(\{2,3\}\)'tür. Buna göre
\[ G = 2^1 - 2^2 - 2^3 + 2^4 = 2 - 4 - 8 + 16 = 6. \]
\(M_5 = 31\) olduğundan
\[ 6^2 = 36 \equiv 5 \pmod{31} \]
olur. Ayrıca \(5 \equiv 5 \pmod 8\) olduğu için küçük kök tam olarak \(G=6\)'dır.
\(q=17\) için aynı yapı \(G=83{,}502\) verir. Karşıt kök
\[ M_{17}-G = 2^{17}-1-83{,}502 = 47{,}569 \]
olur. \(17 \equiv 1 \pmod 8\) olduğu için küçük kök bu kez \(47{,}569\)'dur ve gerçekten
\[ 47{,}569^2 \equiv 17 \pmod{131{,}071}. \]
Uygulama önce \(q\) modundaki sıfır olmayan karesel kalıntılar için bir boolean tablo kurar. Bunun için sadece \(x=1,2,\dots,(q-1)/2\) aralığına bakmak yeterlidir; çünkü \(x^2 \equiv (-x)^2 \pmod q\) olduğundan, bu değerler bütün sıfır olmayan kalıntıları tam bir kez kapsar.
Her kareyi baştan hesaplamak yerine şu değişmez kullanılır:
\[ (x+1)^2 \equiv x^2 + (2x+1) \pmod q. \]
Bu döngü boyunca daima \(2x+1 \le q\) olduğundan, her güncellemede en fazla bir kez \(q\) çıkarmak yeterlidir. Bu ayrıntı, kalıntı üretim aşamasını küçük sabitli gerçek bir \(O(q)\) taramasına dönüştürür.
Sonraki aşamada uygulama \(n=1,2,\dots,q-1\) boyunca tek bir doğrusal tarama yapar ve güncel \(2^n \bmod 10^9+7\) değerini her seferinde bir kez ikiyle çarparak ilerletir.
Eğer \(n\) karesel kalıntıysa bu kuvvet \(G\)'ye eklenir. Eğer karesel kalıntı değilse aynı kuvvet hem \(G\)'den çıkarılır hem de \(N\)'ye eklenir. Böylece tüm matematiksel formül yalnızca modüler toplama ve çıkarma ile tek geçişte hesaplanmış olur.
Önemli nokta şudur: Kod ne \(M_q\)'yu oluşturur ne de dev bir mod altında karekök hesaplayan genel bir yordam çağırır. Sadece kökün açık ikili açılımını değerlendirip sonucu ilerlerken \(10^9+7\) modunda indirger.
Tarama bittiğinde son karar için gereken iki büyüklük hazırdır: \(G\) ve \(N\). İkisi de zaten \(10^9+7\) modunda tutulmuştur.
Eğer \(q \equiv 1 \pmod 8\) ise küçük kök \(1+2N\) olduğundan kod bu değeri döndürür. Aksi halde küçük kök doğrudan \(G\)'dir. C++, Python ve Java uygulamaları aynı matematiksel kararı aynı biçimde uygular.
Algoritma uzunluğu \(q-1\) olan iki doğrusal tarama yapar: biri karesel kalıntıları işaretlemek, diğeri de ağırlıklı 2 kuvvetlerini toplamak için. Bu nedenle toplam çalışma süresi \(O(q)\)'dur.
Bellek kullanımı, kalıntı tablosu nedeniyle \(O(q)\)'dur. Bunun dışında yalnızca birkaç modüler akümülatör ve sayaç tutulur. Hedef asal için doğru denge tam da budur: \(q\) uzunluğunda bir byte tablosu uygulanabilir durumdadır, ama \(M_q\)'nun kendisini temsil etmeye çalışmak astronomik ölçüde pahalı olur.
Sea \(M_q = 2^q - 1\), donde \(q\) es el primo fijado por el problema. Lo que se busca es la raíz cuadrada canónica de \(q\) módulo el número de Mersenne \(M_q\), y luego se pide informar ese entero gigantesco módulo \(10^9+7\).
Un algoritmo directo de raíz cuadrada modular es inviable porque el propio \(M_q\) tiene \(q\) bits. Para el valor objetivo \(q = 74{,}207{,}281\), ni siquiera es realista escribir \(M_q\) de forma explícita. Por eso la solución evita cualquier método genérico y usa en su lugar una suma de caracteres cuyos bits vienen determinados por los residuos cuadráticos módulo \(q\).
La idea central es que, módulo un número de Mersenne, las potencias de 2 se comportan como raíces de la unidad. Eso permite que una suma gaussiana cuadrática se convierta en una expansión binaria explícita de la raíz buscada.
Trabajamos módulo
\[ M_q = 2^q - 1. \]
En este anillo se cumple \(2^q \equiv 1 \pmod{M_q}\), así que los exponentes de 2 pueden reducirse siempre módulo \(q\). Dicho de otro modo, el elemento 2 actúa como una raíz \(q\)-ésima de la unidad no trivial.
Definimos ahora el carácter cuadrático sobre las clases no nulas módulo \(q\):
\[ \chi(a)= \begin{cases} 1, & a \text{ es un residuo cuadrático no nulo módulo } q, \\ -1, & a \text{ es un no residuo cuadrático módulo } q. \end{cases} \]
La suma que evalúan las implementaciones es
\[ G=\sum_{a=1}^{q-1}\chi(a)\,2^a. \]
No es una suma elegida al azar: es exactamente el objeto que codifica la raíz cuadrada.
Expandimos \(G^2\) módulo \(M_q\):
\[ G^2 = \sum_{a=1}^{q-1}\sum_{b=1}^{q-1}\chi(a)\chi(b)\,2^{a+b}. \]
Para cada \(a \ne 0\), escribimos \(b \equiv at \pmod q\). Como \(\chi(ab)=\chi(a)\chi(b)=\chi(t)\) y los exponentes pueden reducirse módulo \(q\), obtenemos
\[ G^2 \equiv \sum_{a=1}^{q-1}\sum_{t=1}^{q-1}\chi(t)\,2^{a(1+t)} \pmod{M_q}. \]
Ahora aparecen dos casos.
Si \(t \not\equiv -1 \pmod q\), entonces multiplicar por \(1+t\) permuta las clases no nulas, y por tanto
\[ \sum_{a=1}^{q-1}2^{a(1+t)} \equiv \sum_{u=1}^{q-1}2^u = 2^q-2 = M_q-1 \equiv -1 \pmod{M_q}. \]
Si \(t \equiv -1 \pmod q\), todos los exponentes se vuelven 0 módulo \(q\), así que la suma interior vale simplemente \(q-1\).
En consecuencia,
\[ G^2 \equiv \chi(-1)(q-1) - \sum_{t \ne -1}\chi(t) \pmod{M_q}. \]
Como el carácter cuadrático toma tantas veces \(+1\) como \(-1\), se tiene
\[ \sum_{t=1}^{q-1}\chi(t)=0. \]
Entonces \(\sum_{t \ne -1}\chi(t) = -\chi(-1)\), y aparece la identidad clásica
\[ G^2 \equiv \chi(-1)\,q = (-1)^{(q-1)/2}q \pmod{M_q}. \]
Para el primo de esta tarea, \(q \equiv 1 \pmod 4\), así que \(\chi(-1)=1\) y
\[ G^2 \equiv q \pmod{M_q}. \]
Por tanto, \(G\) es una de las dos raíces cuadradas de \(q\) módulo \(M_q\).
Definamos
\[ R=\sum_{\chi(a)=1}2^a, \qquad N=\sum_{\chi(a)=-1}2^a. \]
Entonces \(G = R - N\), y además
\[ R+N=\sum_{a=1}^{q-1}2^a = M_q - 1. \]
Por ello
\[ G = M_q - 1 - 2N, \qquad M_q - G = 1 + 2N. \]
Eso significa que, una vez conocida la suma sobre no residuos, la raíz opuesta se obtiene sin costo adicional.
La elección entre \(G\) y \(M_q-G\) depende de \(q \bmod 8\).
El bit más alto \(2^{q-1}\) siempre aparece con signo positivo en \(G\), porque
\[ \chi(q-1)=\chi(-1)=1. \]
El siguiente bit \(2^{q-2}\) tiene signo \(\chi(q-2)=\chi(-2)=\chi(2)\), y la ley suplementaria da
\[ \chi(2)=(-1)^{(q^2-1)/8} = \begin{cases} 1, & q \equiv 1 \pmod 8, \\ -1, & q \equiv 5 \pmod 8. \end{cases} \]
Si \(q \equiv 1 \pmod 8\), incluso en el peor caso para los bits inferiores,
\[ G \ge 2^{q-1}+2^{q-2}-(2^{q-2}-2)=2^{q-1}+2, \]
de modo que \(G > M_q/2\). En ese caso, la raíz menor es
\[ M_q-G = 1+2N. \]
Si \(q \equiv 5 \pmod 8\), incluso favoreciendo todos los bits inferiores,
\[ G \le 2^{q-1}-2^{q-2}+(2^{q-2}-2)=2^{q-1}-2, \]
así que \(G < M_q/2\). Entonces la raíz menor es el propio \(G\).
Para \(q=5\), los residuos cuadráticos no nulos son \(\{1,4\}\) y los no residuos son \(\{2,3\}\). Así,
\[ G = 2^1 - 2^2 - 2^3 + 2^4 = 2 - 4 - 8 + 16 = 6. \]
Como \(M_5 = 31\), se cumple
\[ 6^2 = 36 \equiv 5 \pmod{31}. \]
Además \(5 \equiv 5 \pmod 8\), por lo que la raíz menor es precisamente \(G=6\).
Para \(q=17\), la misma construcción produce \(G=83{,}502\). La raíz opuesta es
\[ M_{17}-G = 2^{17}-1-83{,}502 = 47{,}569. \]
Dado que \(17 \equiv 1 \pmod 8\), la raíz menor es \(47{,}569\), y efectivamente
\[ 47{,}569^2 \equiv 17 \pmod{131{,}071}. \]
La implementación empieza construyendo una tabla booleana de residuos cuadráticos no nulos módulo \(q\). Solo hace falta iterar \(x=1,2,\dots,(q-1)/2\), porque \(x^2 \equiv (-x)^2 \pmod q\), y por tanto esos valores ya recorren cada residuo no nulo exactamente una vez.
En lugar de recalcular cada cuadrado, se mantiene la invariante
\[ (x+1)^2 \equiv x^2 + (2x+1) \pmod q. \]
Durante ese bucle siempre se cumple \(2x+1 \le q\), así que cada actualización necesita como máximo una sola resta de \(q\). Esa observación convierte la fase de marcado en un recorrido \(O(q)\) muy compacto.
Después, la implementación recorre \(n=1,2,\dots,q-1\). En cada paso actualiza la potencia actual \(2^n \bmod 10^9+7\) con una simple duplicación.
Si \(n\) es un residuo cuadrático, esa potencia se suma al acumulador de \(G\). Si \(n\) es un no residuo, la misma potencia se resta de \(G\) y además se suma al acumulador de \(N\). De esta manera, toda la fórmula matemática se evalúa en una sola pasada lineal usando solo sumas y restas modulares.
Lo esencial es que el código nunca construye \(M_q\) y nunca llama a una rutina genérica de raíz cuadrada en un módulo gigantesco. Solo evalúa la expansión binaria explícita de la raíz y va reduciendo el resultado módulo \(10^9+7\).
Al terminar el barrido, la implementación ya dispone exactamente de las dos cantidades necesarias para decidir: \(G\) y \(N\), ambas reducidas módulo \(10^9+7\).
Si \(q \equiv 1 \pmod 8\), la raíz menor es \(1+2N\), y ese es el valor devuelto. En caso contrario, la raíz menor es \(G\). Las versiones en C++, Python y Java siguen exactamente esta misma lógica.
El algoritmo realiza dos recorridos lineales de longitud \(q-1\): uno para marcar los residuos cuadráticos y otro para acumular las potencias ponderadas de 2. Por tanto, el tiempo total es \(O(q)\).
El uso de memoria es \(O(q)\) por la tabla de residuos. Fuera de esa tabla, solo se almacenan unos pocos acumuladores modulares y contadores. Para el primo objetivo, esa es la estrategia correcta: una tabla de bytes de tamaño \(q\) es factible, mientras que representar el propio \(M_q\) está completamente fuera de alcance.
设 \(M_q = 2^q - 1\)，其中 \(q\) 是题目给定的素数。题目要求求出 \(q\) 在 Mersenne 模数 \(M_q\) 下的规范平方根，再把这个极其巨大的整数对 \(10^9+7\) 取模输出。
如果把它理解成“在模 \(M_q\) 下直接开平方”，那几乎没有可操作性，因为 \(M_q\) 本身就有 \(q\) 个二进制位。对于目标值 \(q = 74{,}207{,}281\)，连把 \(M_q\) 明确写出来都不现实。真正可行的办法不是通用的模平方根算法，而是把答案改写成一个由模 \(q\) 二次剩余控制符号的二进制和式。
整个解法的核心，是把“模 Mersenne 数的平方根”问题转化成一个二次特征和。因为在模 \(2^q-1\) 的世界里，2 的幂天然带有 \(q\) 次单位根的结构，这个特征和会直接展开成目标平方根的二进制表示。
我们在如下模数下工作：
\[ M_q = 2^q - 1. \]
在这个剩余类环中有
\[ 2^q \equiv 1 \pmod{M_q}. \]
这意味着 2 的指数在模 \(M_q\) 的意义下总可以按 \(q\) 取模来化简。也就是说，2 在这里扮演的是一个非平凡 \(q\) 次单位根的角色。
接下来在模 \(q\) 的非零剩余类上定义二次特征：
\[ \chi(a)= \begin{cases} 1, & a \text{ 是非零二次剩余}, \\ -1, & a \text{ 是二次非剩余}. \end{cases} \]
程序真正计算的对象是
\[ G=\sum_{a=1}^{q-1}\chi(a)\,2^a. \]
这不是一个随手拼出来的权重和，而是题目答案的核心表达式。
先把 \(G^2\) 展开：
\[ G^2 = \sum_{a=1}^{q-1}\sum_{b=1}^{q-1}\chi(a)\chi(b)\,2^{a+b}. \]
对于每个固定的非零 \(a\)，令 \(b \equiv at \pmod q\)。由于 \(\chi(ab)=\chi(a)\chi(b)=\chi(t)\)，而指数又可以按 \(q\) 取模，于是有
\[ G^2 \equiv \sum_{a=1}^{q-1}\sum_{t=1}^{q-1}\chi(t)\,2^{a(1+t)} \pmod{M_q}. \]
这时只需要分成两种情况讨论。
如果 \(t \not\equiv -1 \pmod q\)，那么乘以 \(1+t\) 会把模 \(q\) 的非零剩余类重新排列一遍，因此
\[ \sum_{a=1}^{q-1}2^{a(1+t)} \equiv \sum_{u=1}^{q-1}2^u = 2^q-2 = M_q-1 \equiv -1 \pmod{M_q}. \]
如果 \(t \equiv -1 \pmod q\)，那么 \(a(1+t)\) 全部都变成 0 模 \(q\)，所以内层和就是 \(q-1\)。
因此可以得到
\[ G^2 \equiv \chi(-1)(q-1)-\sum_{t\ne -1}\chi(t) \pmod{M_q}. \]
而二次特征在 \(1\) 和 \(-1\) 之间取值次数相同，因此
\[ \sum_{t=1}^{q-1}\chi(t)=0. \]
于是 \(\sum_{t\ne -1}\chi(t)=-\chi(-1)\)，最后得到经典结论
\[ G^2 \equiv \chi(-1)\,q = (-1)^{(q-1)/2}q \pmod{M_q}. \]
对本题目标素数而言，\(q \equiv 1 \pmod 4\)，所以 \(\chi(-1)=1\)，从而
\[ G^2 \equiv q \pmod{M_q}. \]
这说明 \(G\) 正是 \(q\) 在模 \(M_q\) 下的两个平方根之一。
把二次剩余和非剩余对应的幂分别记为
\[ R=\sum_{\chi(a)=1}2^a, \qquad N=\sum_{\chi(a)=-1}2^a. \]
那么
\[ G = R-N, \]
而总和满足
\[ R+N=\sum_{a=1}^{q-1}2^a = M_q - 1. \]
所以立刻有
\[ G = M_q - 1 - 2N, \qquad M_q-G = 1+2N. \]
也就是说，只要顺手维护好非剩余部分的和 \(N\)，另一个平方根就已经自动得到了。
剩下的问题是：较小的正根到底是 \(G\) 还是 \(M_q-G\)？这完全由 \(q \bmod 8\) 决定。
\(G\) 的最高位 \(2^{q-1}\) 一定带正号，因为
\[ \chi(q-1)=\chi(-1)=1. \]
次高位 \(2^{q-2}\) 的符号则是 \(\chi(q-2)=\chi(-2)=\chi(2)\)。由二次互反律的辅助定律可知
\[ \chi(2)=(-1)^{(q^2-1)/8} = \begin{cases} 1, & q \equiv 1 \pmod 8, \\ -1, & q \equiv 5 \pmod 8. \end{cases} \]
如果 \(q \equiv 1 \pmod 8\)，那么即使把更低位全部看成最不利的负贡献，也仍有
\[ G \ge 2^{q-1}+2^{q-2}-(2^{q-2}-2)=2^{q-1}+2, \]
因此 \(G > M_q/2\)。这时较小的正根就是
\[ M_q-G = 1+2N. \]
如果 \(q \equiv 5 \pmod 8\)，那么即使把所有更低位都当成有利的正贡献，也只有
\[ G \le 2^{q-1}-2^{q-2}+(2^{q-2}-2)=2^{q-1}-2, \]
所以 \(G < M_q/2\)。这种情况下较小的正根就是 \(G\) 本身。
先看 \(q=5\)。模 5 的非零二次剩余是 \(\{1,4\}\)，二次非剩余是 \(\{2,3\}\)。于是
\[ G = 2^1 - 2^2 - 2^3 + 2^4 = 2 - 4 - 8 + 16 = 6. \]
由于 \(M_5=31\)，可以直接验证
\[ 6^2 = 36 \equiv 5 \pmod{31}. \]
又因为 \(5 \equiv 5 \pmod 8\)，所以较小的根就是 \(G=6\)。
再看 \(q=17\)。同样的构造得到 \(G=83{,}502\)，而相反的根是
\[ M_{17}-G = 2^{17}-1-83{,}502 = 47{,}569. \]
因为 \(17 \equiv 1 \pmod 8\)，较小的正根是 \(47{,}569\)。确实有
\[ 47{,}569^2 \equiv 17 \pmod{131{,}071}. \]
实现首先构造模 \(q\) 的非零二次剩余布尔表。只需要遍历 \(x=1,2,\dots,(q-1)/2\)，因为 \(x^2 \equiv (-x)^2 \pmod q\)，所以这一半已经恰好覆盖了每个非零二次剩余一次。
程序并不是每次都重新计算平方，而是维护递推不变量
\[ (x+1)^2 \equiv x^2 + (2x+1) \pmod q. \]
在这个循环里始终有 \(2x+1 \le q\)，因此每一步更新最多只需要减去一次 \(q\)。这正是剩余标记阶段可以做到紧凑 \(O(q)\) 的原因。
接着，实现对 \(n=1,2,\dots,q-1\) 做一次顺序扫描，并通过不断乘 2 来维护当前的 \(2^n \bmod 10^9+7\)。
如果 \(n\) 是二次剩余，就把这一项加到 \(G\) 上；如果 \(n\) 是二次非剩余，就把这一项从 \(G\) 中减掉，同时加到 \(N\) 上。于是整个数学公式就在一次线性循环里完成了，只涉及模加法与模减法。
最关键的一点是，实现从头到尾都没有构造 \(M_q\)，也没有去做巨型模数下的通用开平方。它只是把答案对应的显式二进制展开逐项求值，并在过程中直接对 \(10^9+7\) 取模。
扫描结束后，程序已经拿到了最后分支需要的全部信息：\(G\) 和 \(N\)，而且二者都已经在输出模数下维护好了。
如果 \(q \equiv 1 \pmod 8\)，较小的根是 \(1+2N\)，于是返回这个值；否则较小的根就是 \(G\)。C++、Python 和 Java 三个实现都遵循同一条数学逻辑。
算法总共进行了两个长度为 \(q-1\) 的线性扫描：一个用于标记二次剩余，一个用于累加加权的 2 次幂。因此总时间复杂度是 \(O(q)\)。
空间复杂度是 \(O(q)\)，主要来自二次剩余表。除此之外，只需要少量模累加器和循环变量。对于目标素数而言，这是合理的资源分配：长度为 \(q\) 的字节表是可行的，而显式表示 \(M_q\) 本身则完全不现实。
Пусть \(M_q = 2^q - 1\), где \(q\) — простое число из условия. Требуется найти канонический квадратный корень из \(q\) по модулю числа Мерсенна \(M_q\), а затем вывести этот огромный результат по модулю \(10^9+7\).
Прямой алгоритм извлечения квадратного корня по модулю \(M_q\) здесь бесполезен, потому что само \(M_q\) имеет \(q\) двоичных разрядов. Для целевого значения \(q = 74{,}207{,}281\) нереально даже выписать модуль целиком. Поэтому решение не использует общий аппарат модульных корней, а строит ответ как специальную сумму, знаки которой задаются квадратичными вычетами по модулю \(q\).
Ключевая идея в том, что по модулю числа Мерсенна степени двойки ведут себя как корни из единицы. Благодаря этому классическая квадратичная сумма Гаусса превращается в явную двоичную запись искомого квадратного корня.
Мы работаем по модулю
\[ M_q = 2^q - 1. \]
В этом кольце выполняется \(2^q \equiv 1 \pmod{M_q}\), значит, показатели степеней двойки можно всегда сокращать по модулю \(q\). Иными словами, число 2 играет роль нетривиального \(q\)-го корня из единицы.
Определим квадратичный характер на ненулевых классах по модулю \(q\):
\[ \chi(a)= \begin{cases} 1, & a \text{ — ненулевой квадратичный вычет mod } q, \\ -1, & a \text{ — квадратичный невычет mod } q. \end{cases} \]
Основная сумма, которую вычисляет реализация, имеет вид
\[ G=\sum_{a=1}^{q-1}\chi(a)\,2^a. \]
Именно она и кодирует искомый корень.
Раскроем квадрат:
\[ G^2 = \sum_{a=1}^{q-1}\sum_{b=1}^{q-1}\chi(a)\chi(b)\,2^{a+b}. \]
Для каждого фиксированного \(a \ne 0\) положим \(b \equiv at \pmod q\). Тогда \(\chi(ab)=\chi(a)\chi(b)=\chi(t)\), а показатели можно сокращать по модулю \(q\). Получаем
\[ G^2 \equiv \sum_{a=1}^{q-1}\sum_{t=1}^{q-1}\chi(t)\,2^{a(1+t)} \pmod{M_q}. \]
Теперь нужно рассмотреть два случая.
Если \(t \not\equiv -1 \pmod q\), то умножение на \(1+t\) переставляет все ненулевые классы, поэтому
\[ \sum_{a=1}^{q-1}2^{a(1+t)} \equiv \sum_{u=1}^{q-1}2^u = 2^q-2 = M_q-1 \equiv -1 \pmod{M_q}. \]
Если же \(t \equiv -1 \pmod q\), то все показатели превращаются в 0 по модулю \(q\), и внутренняя сумма равна просто \(q-1\).
Следовательно,
\[ G^2 \equiv \chi(-1)(q-1)-\sum_{t \ne -1}\chi(t) \pmod{M_q}. \]
Поскольку квадратичный характер принимает значения \(+1\) и \(-1\) поровну часто, имеем
\[ \sum_{t=1}^{q-1}\chi(t)=0. \]
Значит, \(\sum_{t \ne -1}\chi(t)=-\chi(-1)\), и получается стандартная формула
\[ G^2 \equiv \chi(-1)\,q = (-1)^{(q-1)/2}q \pmod{M_q}. \]
Для используемого здесь простого числа \(q \equiv 1 \pmod 4\), поэтому \(\chi(-1)=1\) и
\[ G^2 \equiv q \pmod{M_q}. \]
Тем самым \(G\) является одним из двух квадратных корней из \(q\) по модулю \(M_q\).
Обозначим
\[ R=\sum_{\chi(a)=1}2^a, \qquad N=\sum_{\chi(a)=-1}2^a. \]
Тогда \(G=R-N\), а также
\[ R+N=\sum_{a=1}^{q-1}2^a = M_q - 1. \]
Следовательно,
\[ G = M_q - 1 - 2N, \qquad M_q-G = 1+2N. \]
То есть после вычисления суммы по невычетам величина противоположного корня уже известна автоматически.
Остается понять, какая из двух величин, \(G\) или \(M_q-G\), является меньшим положительным корнем. Это определяется остатком \(q \bmod 8\).
Старший двоичный разряд \(2^{q-1}\) всегда входит в \(G\) с плюсом, потому что
\[ \chi(q-1)=\chi(-1)=1. \]
Знак следующего разряда \(2^{q-2}\) равен \(\chi(q-2)=\chi(-2)=\chi(2)\), а дополнительный закон дает
\[ \chi(2)=(-1)^{(q^2-1)/8} = \begin{cases} 1, & q \equiv 1 \pmod 8, \\ -1, & q \equiv 5 \pmod 8. \end{cases} \]
Если \(q \equiv 1 \pmod 8\), то даже при максимально неблагоприятном хвосте
\[ G \ge 2^{q-1}+2^{q-2}-(2^{q-2}-2)=2^{q-1}+2, \]
поэтому \(G > M_q/2\). Значит, меньшим корнем будет
\[ M_q-G = 1+2N. \]
Если \(q \equiv 5 \pmod 8\), то даже в максимально благоприятном случае
\[ G \le 2^{q-1}-2^{q-2}+(2^{q-2}-2)=2^{q-1}-2, \]
то есть \(G < M_q/2\). Тогда меньший корень — это сам \(G\).
Для \(q=5\) ненулевые квадратичные вычеты — это \(\{1,4\}\), а невычеты — \(\{2,3\}\). Поэтому
\[ G = 2^1 - 2^2 - 2^3 + 2^4 = 2 - 4 - 8 + 16 = 6. \]
Поскольку \(M_5 = 31\), имеем
\[ 6^2 = 36 \equiv 5 \pmod{31}. \]
Кроме того, \(5 \equiv 5 \pmod 8\), значит, меньший корень — именно \(G=6\).
Для \(q=17\) та же конструкция дает \(G=83{,}502\). Противоположный корень равен
\[ M_{17}-G = 2^{17}-1-83{,}502 = 47{,}569. \]
Так как \(17 \equiv 1 \pmod 8\), меньшим корнем оказывается \(47{,}569\), и действительно
\[ 47{,}569^2 \equiv 17 \pmod{131{,}071}. \]
Сначала реализация строит булеву таблицу ненулевых квадратичных вычетов по модулю \(q\). Достаточно пройти по \(x=1,2,\dots,(q-1)/2\), поскольку \(x^2 \equiv (-x)^2 \pmod q\), а значит, эти значения уже дают каждый ненулевой вычет ровно один раз.
Каждый квадрат не пересчитывается заново. Вместо этого используется инвариант
\[ (x+1)^2 \equiv x^2 + (2x+1) \pmod q. \]
Во всем этом цикле всегда выполняется \(2x+1 \le q\), поэтому на каждом шаге достаточно не более одного вычитания \(q\). Именно это делает фазу построения таблицы плотным линейным проходом.
Далее реализация один раз проходит по \(n=1,2,\dots,q-1\), поддерживая текущее значение \(2^n \bmod 10^9+7\) обычным удвоением.
Если \(n\) отмечено как квадратичный вычет, соответствующая степень добавляется к накопителю \(G\). Если же \(n\) — невычет, то та же степень вычитается из \(G\) и одновременно добавляется к \(N\). Таким образом, вся математическая формула вычисляется за один линейный проход при помощи только модульных сложений и вычитаний.
Существенно, что код никогда не строит само \(M_q\) и не вызывает универсальную процедуру квадратного корня по огромному модулю. Он просто вычисляет явную двоичную запись ответа и сразу же сводит ее по модулю \(10^9+7\).
После завершения прохода реализация уже имеет обе величины, нужные для выбора: \(G\) и \(N\), причем обе уже приведены по модулю \(10^9+7\).
Если \(q \equiv 1 \pmod 8\), меньший корень равен \(1+2N\), и возвращается именно это значение. В противном случае меньшим корнем является \(G\). Реализации на C++, Python и Java следуют одной и той же математической схеме.
Алгоритм выполняет два линейных прохода длины \(q-1\): один для построения таблицы квадратичных вычетов и один для накопления взвешенных степеней двойки. Следовательно, время работы равно \(O(q)\).
Память составляет \(O(q)\) из-за таблицы вычетов. Помимо нее хранятся лишь несколько модульных аккумуляторов и счетчиков. Для целевого простого числа это оптимальный компромисс: массив длины \(q\) еще практичен, а попытка явно представлять \(M_q\) была бы совершенно нереалистичной.
لنكتب \(M_q = 2^q - 1\)، حيث إن \(q\) هو العدد الأولي المعطى في المسألة. المطلوب هو إيجاد الجذر التربيعي القياسي للعدد \(q\) بترديد عدد ميرسن \(M_q\)، ثم إرجاع هذا العدد الضخم بترديد \(10^9+7\).
أي محاولة لاستخراج جذر تربيعي مباشرة بترديد \(M_q\) غير عملية، لأن \(M_q\) نفسه يملك \(q\) خانة ثنائية. وعند القيمة المستهدفة \(q = 74{,}207{,}281\) يصبح حتى تمثيل \(M_q\) نفسه صراحة أمرًا غير واقعي. لذلك لا تستعمل الحلول أي خوارزمية عامة للجذور المعيارية، بل تعيد كتابة الجواب على هيئة مجموع تتحدد إشاراته بواسطة البواقي التربيعية modulo \(q\).
الفكرة الأساسية هي أن قوى العدد 2 بترديد عدد ميرسن تتصرف كما لو كانت جذورًا للوحدة. وبسبب هذا تتحول صيغة كلاسيكية من نوع مجموع غاوس التربيعي إلى تمثيل ثنائي صريح للجذر المطلوب.
نحن نعمل بترديد
\[ M_q = 2^q - 1. \]
في هذا النظام يتحقق
\[ 2^q \equiv 1 \pmod{M_q}. \]
وهذا يعني أن أسس العدد 2 يمكن اختزالها دائمًا modulo \(q\). أي إن العدد 2 يلعب هنا دور جذر وحدة غير تافه من الرتبة \(q\).
نعرّف الآن المحرف التربيعي على الأصناف غير الصفرية modulo \(q\):
\[ \chi(a)= \begin{cases} 1, & a \text{ is a nonzero quadratic residue mod } q, \\ -1, & a \text{ is a quadratic non-residue mod } q. \end{cases} \]
المجموع المركزي الذي تحسبه التطبيقات هو
\[ G=\sum_{a=1}^{q-1}\chi(a)\,2^a. \]
وهذا ليس مجرد مجموع موزون اعتباطي، بل هو التعبير الذي يحمل الجذر التربيعي نفسه.
لنوسع مربع \(G\):
\[ G^2 = \sum_{a=1}^{q-1}\sum_{b=1}^{q-1}\chi(a)\chi(b)\,2^{a+b}. \]
لكل \(a \ne 0\)، نكتب \(b \equiv at \pmod q\). وبما أن \(\chi(ab)=\chi(a)\chi(b)=\chi(t)\)، وبما أن الأسس يمكن اختزالها modulo \(q\)، نحصل على
\[ G^2 \equiv \sum_{a=1}^{q-1}\sum_{t=1}^{q-1}\chi(t)\,2^{a(1+t)} \pmod{M_q}. \]
من هنا تظهر حالتان.
إذا كان \(t \not\equiv -1 \pmod q\)، فإن الضرب في \(1+t\) يعيد ترتيب جميع الأصناف غير الصفرية، ولذلك
\[ \sum_{a=1}^{q-1}2^{a(1+t)} \equiv \sum_{u=1}^{q-1}2^u = 2^q-2 = M_q-1 \equiv -1 \pmod{M_q}. \]
أما إذا كان \(t \equiv -1 \pmod q\)، فإن جميع الأسس تصبح صفرًا modulo \(q\)، وعندها يكون المجموع الداخلي مساويًا لـ \(q-1\).
إذن
\[ G^2 \equiv \chi(-1)(q-1)-\sum_{t \ne -1}\chi(t) \pmod{M_q}. \]
ولأن المحرف التربيعي يأخذ القيمتين \(+1\) و\(-1\) بعدد متساوٍ، فإن
\[ \sum_{t=1}^{q-1}\chi(t)=0. \]
ومن ثم \(\sum_{t \ne -1}\chi(t)=-\chi(-1)\)، فنحصل على الهوية المعروفة
\[ G^2 \equiv \chi(-1)\,q = (-1)^{(q-1)/2}q \pmod{M_q}. \]
وفي هذه المسألة يكون \(q \equiv 1 \pmod 4\)، لذا \(\chi(-1)=1\) ومن ثم
\[ G^2 \equiv q \pmod{M_q}. \]
أي إن \(G\) هو أحد الجذرين التربيعيين للعدد \(q\) modulo \(M_q\).
لنعرّف
\[ R=\sum_{\chi(a)=1}2^a, \qquad N=\sum_{\chi(a)=-1}2^a. \]
عندئذٍ
\[ G = R-N, \]
وفي الوقت نفسه
\[ R+N=\sum_{a=1}^{q-1}2^a = M_q - 1. \]
إذن
\[ G = M_q - 1 - 2N, \qquad M_q-G = 1+2N. \]
وهذا يعني أن معرفة مجموع اللا-بواقي التربيعية \(N\) تكفي أيضًا لإعطاء الجذر المقابل فورًا.
يبقى تحديد أيهما أصغر: \(G\) أم \(M_q-G\). هذا يعتمد فقط على \(q \bmod 8\).
البت الأعلى \(2^{q-1}\) يظهر دائمًا بإشارة موجبة داخل \(G\)، لأن
\[ \chi(q-1)=\chi(-1)=1. \]
أما البت التالي \(2^{q-2}\) فإشارته هي \(\chi(q-2)=\chi(-2)=\chi(2)\)، ويعطي القانون التكميلي
\[ \chi(2)=(-1)^{(q^2-1)/8} = \begin{cases} 1, & q \equiv 1 \pmod 8, \\ -1, & q \equiv 5 \pmod 8. \end{cases} \]
إذا كان \(q \equiv 1 \pmod 8\)، فحتى مع أسوأ مساهمة ممكنة من جميع البتات الأدنى نحصل على
\[ G \ge 2^{q-1}+2^{q-2}-(2^{q-2}-2)=2^{q-1}+2, \]
ومن ثم \(G > M_q/2\). عندها يكون الجذر الأصغر هو
\[ M_q-G = 1+2N. \]
أما إذا كان \(q \equiv 5 \pmod 8\)، فحتى مع أفضل مساهمة ممكنة من الذيل كله يبقى
\[ G \le 2^{q-1}-2^{q-2}+(2^{q-2}-2)=2^{q-1}-2, \]
أي \(G < M_q/2\). في هذه الحالة يكون \(G\) نفسه هو الجذر الأصغر.
عندما \(q=5\)، تكون البواقي التربيعية غير الصفرية هي \(\{1,4\}\)، واللا-بواقي هي \(\{2,3\}\). لذلك
\[ G = 2^1 - 2^2 - 2^3 + 2^4 = 2 - 4 - 8 + 16 = 6. \]
وبما أن \(M_5 = 31\)، فنجد
\[ 6^2 = 36 \equiv 5 \pmod{31}. \]
ولأن \(5 \equiv 5 \pmod 8\)، فإن الجذر الأصغر هو بالضبط \(G=6\).
وعندما \(q=17\)، تعطي البنية نفسها القيمة \(G=83{,}502\)، ويكون الجذر المقابل
\[ M_{17}-G = 2^{17}-1-83{,}502 = 47{,}569. \]
وبما أن \(17 \equiv 1 \pmod 8\)، فإن الجذر الأصغر هو \(47{,}569\)، وبالفعل
\[ 47{,}569^2 \equiv 17 \pmod{131{,}071}. \]
تبدأ الشيفرة ببناء جدول منطقي للبواقي التربيعية غير الصفرية modulo \(q\). ويكفي المرور على \(x=1,2,\dots,(q-1)/2\)، لأن \(x^2 \equiv (-x)^2 \pmod q\)، وبذلك نحصل على كل بقايا تربيعية غير صفرية مرة واحدة تمامًا.
ولا يُعاد حساب كل مربع من البداية، بل تُستعمل العلاقة الثابتة
\[ (x+1)^2 \equiv x^2 + (2x+1) \pmod q. \]
وطوال هذه الحلقة لدينا دائمًا \(2x+1 \le q\)، لذلك تكفي في كل خطوة عملية طرح واحدة على الأكثر من \(q\). وهذه نقطة مهمة لأنها تجعل مرحلة توليد الجدول مرحلة \(O(q)\) فعلية وبثابت صغير.
بعد ذلك تمر الشيفرة على \(n=1,2,\dots,q-1\) مرة واحدة، وتحافظ على القيمة الحالية لـ \(2^n \bmod 10^9+7\) عبر مضاعفة متكررة.
إذا كان \(n\) بقايا تربيعية، فإن هذه القوة تضاف إلى المجمع الخاص بـ \(G\). وإذا كان \(n\) لا-بقايا تربيعية، فإن هذه القوة نفسها تُطرح من \(G\) وتُضاف في الوقت ذاته إلى \(N\). وهكذا تُحسب الصيغة الرياضية كاملة في مرور خطي واحد باستخدام جمع وطرح معياريين فقط.
النقطة الحاسمة هي أن التطبيق لا يبني \(M_q\) أبدًا، ولا يستدعي إجراء عامًا لاستخراج جذر تربيعي modulo عدد هائل. بل يقيّم التمثيل الثنائي الصريح للجذر المطلوب ويختزل الناتج مباشرة modulo \(10^9+7\) أثناء السير.
عند نهاية المرور تكون القيمتان اللازمتان للحسم جاهزتين: \(G\) و\(N\)، وكلتاهما محفوظة بالفعل modulo \(10^9+7\).
إذا كان \(q \equiv 1 \pmod 8\)، فالجذر الأصغر هو \(1+2N\)، ولذلك تُعاد هذه القيمة. أما في غير ذلك فالجذر الأصغر هو \(G\) نفسه. وتطبق نسخ C++ وPython وJava هذه القاعدة الرياضية نفسها دون اختلاف.
تنفذ الخوارزمية مرورين خطيين بطول \(q-1\): الأول لتعليم البواقي التربيعية، والثاني لتجميع قوى العدد 2 الموزونة. لذلك يكون زمن التنفيذ الكلي \(O(q)\).
استهلاك الذاكرة هو \(O(q)\) بسبب جدول البواقي. وما عدا هذا الجدول لا يُخزَّن إلا عدد قليل من المجمعات المعيارية والعدادات. وبالنسبة إلى العدد الأولي المستهدف فهذا هو التوازن الصحيح تمامًا: جدول بايتات بطول \(q\) قابل للتطبيق، بينما تمثيل \(M_q\) نفسه صراحة أمر بعيد تمامًا عن الإمكان.