We are given a 48-bit linear congruential generator with state update
$$a_{n+1}=A a_n + C \pmod{2^{48}},\qquad A=25214903917,\quad C=11.$$
Each state emits one letter from a 52-symbol alphabet by taking the upper 32 bits, reducing them modulo \(52\), and mapping \(0,\dots,25\) to a through z and \(26,\dots,51\) to A through Z. The problem asks for the exact step distance between the two target words that appear in this sequence. Since the generator has period \(2^{48}\), direct simulation is not realistic; the solution instead reconstructs the unique starting state of each target word and then computes the distance algebraically.
Let the emitted code at time \(n\) be
$$u_n=\left\lfloor\frac{a_n}{2^{16}}\right\rfloor \bmod 52.$$
For a target word with code sequence \(t_0,t_1,\dots,t_{m-1}\), we must find all starting states \(a_0\) such that
$$u_i=t_i\qquad (0 \le i \lt m).$$
Write every state as
$$a_n=2^{16}q_n+\ell_n,\qquad 0\le \ell_n \lt 2^{16},\qquad 0\le q_n \lt 2^{32}.$$
Substituting this into the recurrence separates the dynamics into a low 16-bit part and a high 32-bit part. The low word evolves by
$$\ell_{n+1}\equiv A\ell_n+C \pmod{2^{16}},$$
and the carry into the high word is
$$\kappa_n=\left\lfloor\frac{A\ell_n+C}{2^{16}}\right\rfloor.$$
The high word therefore satisfies
$$q_{n+1}\equiv A q_n+\kappa_n \pmod{2^{32}}.$$
The output condition depends only on \(q_n\):
$$q_n\equiv t_n \pmod{52}.$$
This decomposition is the key observation: the entire carry sequence is determined by the starting low word \(\ell_0\), while the starting high word \(q_0\) only has to satisfy a linear recurrence modulo \(2^{32}\).
The implementation first exploits a very cheap necessary condition. Since \(A\equiv 1 \pmod 4\), reducing the high-word recurrence modulo \(4\) gives
$$q_{n+1}-q_n\equiv \kappa_n \pmod 4.$$
Because \(q_n\equiv t_n \pmod{52}\), this implies
$$\kappa_n\equiv t_{n+1}-t_n \pmod 4.$$
So each adjacent pair of target characters prescribes the carry residue modulo \(4\). The low word \(\ell_0\) can take only \(2^{16}\) possible values, and for each one the low recurrence produces a deterministic carry sequence. Any starting low word whose carry residues fail even one of these congruences is impossible and can be discarded immediately.
This turns the first stage into a complete scan of only \(65536\) candidates, which is tiny compared with the full \(2^{48}\)-state space.
Once a starting low word survives the modulo-\(4\) filter, the exact carries \(\kappa_0,\kappa_1,\dots,\kappa_{m-2}\) are known. The starting high word must satisfy
$$q_0\equiv t_0 \pmod{52},$$
so we can write
$$q_0=t_0+52r,\qquad 0\le q_0 \lt 2^{32}.$$
For each such candidate, we iterate
$$q_{i+1}\equiv A q_i+\kappa_i \pmod{2^{32}}$$
and check whether every step still satisfies \(q_i\equiv t_i \pmod{52}\). Every successful \(q_0\) yields a full starting state
$$a_0=2^{16}q_0+\ell_0.$$
For the two actual target words of the problem, this reconstruction returns exactly one valid starting state for each word.
The one-step transition is affine: \(x\mapsto A x+C\). Composing affine maps keeps the same form, so for every nonnegative integer \(s\) there exist coefficients \(\alpha_s\) and \(\beta_s\) such that
$$a_{n+s}=\alpha_s a_n+\beta_s \pmod{2^{48}}.$$
If two affine maps are written as \(x\mapsto \alpha_1 x+\beta_1\) and \(x\mapsto \alpha_2 x+\beta_2\), then their composition is
$$x\mapsto \alpha_1\alpha_2 x+(\alpha_1\beta_2+\beta_1).$$
This means binary exponentiation works exactly as it does for ordinary modular powers: repeated squaring gives \((\alpha_s,\beta_s)\) in \(O(\log s)\) time. The implementation uses this both for verification and for checking the few candidate distances that remain after the discrete-log step.
Define a transformed quantity
$$b_n=(A-1)a_n+C \pmod{2^{48}}.$$
Then
$$\begin{aligned} b_{n+1} &=(A-1)(A a_n+C)+C\\ &=A\bigl((A-1)a_n+C\bigr)\\ &\equiv A b_n \pmod{2^{48}}. \end{aligned}$$
So the affine recurrence becomes a purely multiplicative recurrence. This is the central algebraic simplification.
Moreover, every \(b_n\) is odd. Indeed, \(A-1\) is divisible by \(4\), while \(C=11\) is odd, so \((A-1)a_n+C\equiv 3 \pmod 4\). Therefore \(b_n\) is invertible modulo \(2^{48}\).
If \(s\) and \(t\) are the two reconstructed starting states and \(t\) occurs \(\Delta\) steps after \(s\), then
$$b_t\equiv A^{\Delta} b_s \pmod{2^{48}},$$
hence
$$A^{\Delta}\equiv b_t\,b_s^{-1}\pmod{2^{48}}.$$
The ratio on the right is congruent to \(1 \pmod 4\), so it lies in the relevant cyclic \(2\)-power subgroup generated by \(A\).
Modulo \(2^{48}\), the multiplier \(A\) has order \(2^{46}\) inside the subgroup used above. Therefore the exponent \(\Delta\) is first determined only modulo \(2^{46}\).
The implementation extracts this exponent bit by bit. Suppose the current ratio is \(A^e\). Raising it to \(2^{45-i}\) tells whether bit \(i\) of \(e\) is zero or one: if the result is not \(1\), then bit \(i\) must be \(1\), and the corresponding factor \(A^{2^i}\) is divided out before moving to the next bit. This recovers the base solution
$$\Delta\equiv \Delta_0 \pmod{2^{46}}.$$
However, the map \(a\mapsto (A-1)a+C\) is not injective modulo \(2^{48}\): since \(\gcd(A-1,2^{48})=4\), the transformed sequence identifies four LCG states at a time. Therefore the true distance must be one of
$$\Delta_0,\qquad \Delta_0+2^{46},\qquad \Delta_0+2\cdot 2^{46},\qquad \Delta_0+3\cdot 2^{46}.$$
The affine jump formula from Step 4 checks these four lifts directly and selects the exact step count.
Take a target prefix of length \(2\) with codes \(t_0\) and \(t_1\). A starting low word \(\ell_0\) produces a carry
$$\kappa_0=\left\lfloor\frac{A\ell_0+C}{2^{16}}\right\rfloor.$$
A necessary condition for this low word to work is
$$\kappa_0\equiv t_1-t_0 \pmod 4.$$
Most of the \(2^{16}\) low-word candidates fail this immediately. For each survivor, the high word must lie on the arithmetic progression
$$q_0=t_0+52r.$$
Testing these candidates with the exact 32-bit recurrence either rejects them or produces a genuine starting state. Longer prefixes do the same thing repeatedly, one carry constraint and one high-word update at a time.
The C++, Python, and Java implementations follow the same mathematical pipeline. First they encode letters into numbers \(0\) through \(51\). Then they enumerate all \(2^{16}\) possible low 16-bit starts, simulate only the low-word recurrence, and compare the carry residues modulo \(4\) against the differences forced by the target word.
For every surviving low-word candidate, the implementation recomputes the exact carries and tests the arithmetic progression \(t_0+52r\) of possible high words. Each successful pair of high and low words is assembled into a 48-bit starting state, and duplicate states are removed after sorting.
After both target words have been converted into their unique starting states, the implementation transforms them into odd residues modulo \(2^{48}\), computes a modular inverse, and solves the exponent in the order-\(2^{46}\) subgroup one bit at a time. It then checks the four possible lifts by fast affine jumping, which is much cheaper than iterating the generator step by step.
The language-specific arithmetic details differ slightly. C++ uses a 128-bit intermediate product and masks the result back to 48 bits. Python uses arbitrary-precision integers with the same masking rule. Java avoids overflow in signed 64-bit arithmetic by splitting each 48-bit factor into two 24-bit halves and recombining the partial products before applying the mask.
Let \(m\) be the target-word length, and let \(R\) be the number of starting low words that survive the carry-residue filter. The low-word scan costs \(O(2^{16}m)\). Recomputing the exact carry sequences costs \(O(Rm)\). The high-word search is \(O\!\left(R\left\lceil\frac{2^{32}}{52}\right\rceil m\right)\) in the pessimistic worst case, because each surviving low word is paired with an arithmetic progression of possible 32-bit high words.
In practice, the carry constraints are extremely restrictive, so \(R\) is tiny for the fixed words in this problem, and the reconstruction stage is dominated by the initial \(2^{16}\) scan. The distance phase needs only \(O(\log 2^{48})\) modular multiplications, plus at most four affine-jump verifications. Memory usage is \(O(R+m)\), which is effectively constant for the given input sizes.
Gegeben ist ein 48-Bit-Linear-Congruential-Generator mit der Zustandsaktualisierung
$$a_{n+1}=A a_n + C \pmod{2^{48}},\qquad A=25214903917,\quad C=11.$$
Jeder Zustand liefert einen Buchstaben aus einem Alphabet mit \(52\) Symbolen, indem die oberen \(32\) Bits genommen, modulo \(52\) reduziert und dann \(0,\dots,25\) auf a bis z sowie \(26,\dots,51\) auf A bis Z abgebildet werden. Gesucht ist der exakte Schrittabstand zwischen den beiden Zielwörtern in dieser Folge. Eine direkte Simulation über den gesamten Zyklus der Länge \(2^{48}\) ist unpraktisch; deshalb rekonstruiert die Lösung zunächst die eindeutigen Startzustände der beiden Wörter und bestimmt ihren Abstand anschließend rein algebraisch.
Bezeichne den ausgegebenen Code zum Zeitpunkt \(n\) mit
$$u_n=\left\lfloor\frac{a_n}{2^{16}}\right\rfloor \bmod 52.$$
Für ein Zielwort mit Codefolge \(t_0,t_1,\dots,t_{m-1}\) suchen wir alle Startzustände \(a_0\), für die
$$u_i=t_i\qquad (0 \le i \lt m)$$
gilt.
Schreibe jeden Zustand als
$$a_n=2^{16}q_n+\ell_n,\qquad 0\le \ell_n \lt 2^{16},\qquad 0\le q_n \lt 2^{32}.$$
Setzt man dies in die Rekurrenz ein, trennen sich die Dynamiken des unteren 16-Bit-Teils und des oberen 32-Bit-Teils. Das Low-Wort erfüllt
$$\ell_{n+1}\equiv A\ell_n+C \pmod{2^{16}},$$
und der Übertrag ins High-Wort ist
$$\kappa_n=\left\lfloor\frac{A\ell_n+C}{2^{16}}\right\rfloor.$$
Damit folgt für das High-Wort
$$q_{n+1}\equiv A q_n+\kappa_n \pmod{2^{32}}.$$
Die Ausgabebedingung hängt nur von \(q_n\) ab:
$$q_n\equiv t_n \pmod{52}.$$
Genau hierin liegt der Kern der Methode: Die komplette Übertragsfolge ist bereits durch das Start-Low-Wort \(\ell_0\) festgelegt, während das Start-High-Wort \(q_0\) nur noch eine lineare Rekurrenz modulo \(2^{32}\) erfüllen muss.
Die Implementierung nutzt zunächst eine sehr billige notwendige Bedingung. Da \(A\equiv 1 \pmod 4\), liefert die Reduktion der High-Wort-Rekurrenz modulo \(4\)
$$q_{n+1}-q_n\equiv \kappa_n \pmod 4.$$
Wegen \(q_n\equiv t_n \pmod{52}\) folgt daraus
$$\kappa_n\equiv t_{n+1}-t_n \pmod 4.$$
Also erzwingt jedes benachbarte Zeichenpaar im Zielwort einen Rest des Übertrags modulo \(4\). Das Start-Low-Wort \(\ell_0\) hat nur \(2^{16}\) Möglichkeiten, und für jede davon erzeugt die Low-Rekurrenz eine deterministische Übertragsfolge. Verstößt deren Modulo-\(4\)-Muster auch nur an einer Stelle gegen die Zielvorgabe, kann der Kandidat sofort verworfen werden.
Damit schrumpft die erste Phase auf eine vollständige Durchmusterung von nur \(65536\) Kandidaten, statt den gesamten Raum von \(2^{48}\) Zuständen anfassen zu müssen.
Sobald ein Start-Low-Wort den Modulo-\(4\)-Filter überlebt, sind die exakten Überträge \(\kappa_0,\kappa_1,\dots,\kappa_{m-2}\) bekannt. Das Start-High-Wort muss
$$q_0\equiv t_0 \pmod{52}$$
erfüllen, also schreiben wir
$$q_0=t_0+52r,\qquad 0\le q_0 \lt 2^{32}.$$
Für jeden solchen Kandidaten iterieren wir
$$q_{i+1}\equiv A q_i+\kappa_i \pmod{2^{32}}$$
und prüfen, ob weiterhin \(q_i\equiv t_i \pmod{52}\) gilt. Jeder erfolgreiche Wert von \(q_0\) liefert einen vollständigen Startzustand
$$a_0=2^{16}q_0+\ell_0.$$
Für die beiden tatsächlichen Zielwörter der Aufgabe ergibt diese Rekonstruktion jeweils genau einen gültigen Startzustand.
Der Ein-Schritt-Übergang ist affin: \(x\mapsto A x+C\). Die Komposition affiner Abbildungen bleibt affin, also existieren für jedes nichtnegative \(s\) Koeffizienten \(\alpha_s\) und \(\beta_s\) mit
$$a_{n+s}=\alpha_s a_n+\beta_s \pmod{2^{48}}.$$
Werden zwei affine Abbildungen als \(x\mapsto \alpha_1 x+\beta_1\) bzw. \(x\mapsto \alpha_2 x+\beta_2\) geschrieben, dann ist ihre Komposition
$$x\mapsto \alpha_1\alpha_2 x+(\alpha_1\beta_2+\beta_1).$$
Daher funktioniert binäre Exponentiation genau wie bei gewöhnlichen modularen Potenzen: Durch wiederholtes Quadrieren erhält man \((\alpha_s,\beta_s)\) in \(O(\log s)\). Die Implementierung benutzt dies sowohl zur Verifikation als auch zum Prüfen der wenigen Distanzkandidaten, die nach dem diskreten Logarithmus noch übrig bleiben.
Definiere die transformierte Größe
$$b_n=(A-1)a_n+C \pmod{2^{48}}.$$
Dann gilt
$$\begin{aligned} b_{n+1} &=(A-1)(A a_n+C)+C\\ &=A\bigl((A-1)a_n+C\bigr)\\ &\equiv A b_n \pmod{2^{48}}. \end{aligned}$$
Damit wird die affine Rekurrenz zu einer rein multiplikativen Dynamik. Genau das ist die entscheidende algebraische Vereinfachung.
Außerdem ist jedes \(b_n\) ungerade. Denn \(A-1\) ist durch \(4\) teilbar, während \(C=11\) ungerade ist, also gilt \((A-1)a_n+C\equiv 3 \pmod 4\). Daher besitzt \(b_n\) modulo \(2^{48}\) immer ein Inverses.
Sind \(s\) und \(t\) die beiden rekonstruierten Startzustände und liegt \(t\) genau \(\Delta\) Schritte nach \(s\), so folgt
$$b_t\equiv A^{\Delta} b_s \pmod{2^{48}},$$
also
$$A^{\Delta}\equiv b_t\,b_s^{-1}\pmod{2^{48}}.$$
Der Quotient rechts ist kongruent zu \(1 \pmod 4\) und liegt damit in der relevanten zyklischen \(2\)-Potenz-Untergruppe, die von \(A\) erzeugt wird.
Modulo \(2^{48}\) hat der Multiplikator \(A\) in der verwendeten Untergruppe die Ordnung \(2^{46}\). Deshalb ist der Exponent \(\Delta\) zunächst nur modulo \(2^{46}\) bestimmt.
Die Implementierung rekonstruiert diesen Exponenten Bit für Bit. Ist das aktuelle Verhältnis gleich \(A^e\), dann verrät die Potenzierung mit \(2^{45-i}\), ob Bit \(i\) von \(e\) null oder eins ist: Ist das Ergebnis nicht \(1\), dann muss Bit \(i\) gleich \(1\) sein, und der Faktor \(A^{2^i}\) wird herausdividiert, bevor das nächste Bit betrachtet wird. So erhält man die Basislösung
$$\Delta\equiv \Delta_0 \pmod{2^{46}}.$$
Die Abbildung \(a\mapsto (A-1)a+C\) ist modulo \(2^{48}\) jedoch nicht injektiv: Da \(\gcd(A-1,2^{48})=4\), identifiziert die transformierte Folge jeweils vier LCG-Zustände. Deshalb muss die wahre Distanz eine der vier Zahlen
$$\Delta_0,\qquad \Delta_0+2^{46},\qquad \Delta_0+2\cdot 2^{46},\qquad \Delta_0+3\cdot 2^{46}$$
sein. Die affine Sprungformel aus Schritt 4 prüft diese vier Anhebungen direkt und wählt die exakte Schrittzahl aus.
Nehmen wir ein Zielpräfix der Länge \(2\) mit Codes \(t_0\) und \(t_1\). Ein Start-Low-Wort \(\ell_0\) erzeugt den Übertrag
$$\kappa_0=\left\lfloor\frac{A\ell_0+C}{2^{16}}\right\rfloor.$$
Eine notwendige Bedingung dafür, dass dieses Low-Wort funktionieren kann, lautet
$$\kappa_0\equiv t_1-t_0 \pmod 4.$$
Die meisten der \(2^{16}\) Low-Wort-Kandidaten scheitern schon hier. Für jeden überlebenden Kandidaten muss das High-Wort auf der arithmetischen Progression
$$q_0=t_0+52r$$
liegen. Das Testen dieser Kandidaten mit der exakten 32-Bit-Rekurrenz verwirft sie entweder oder erzeugt einen echten Startzustand. Längere Präfixe wiederholen dieselbe Idee, nur mit einer ganzen Folge von Übertragsbedingungen und High-Wort-Updates.
Die Implementierungen in C++, Python und Java folgen derselben mathematischen Pipeline. Zuerst werden die Buchstaben in Zahlen von \(0\) bis \(51\) kodiert. Danach werden alle \(2^{16}\) möglichen Startwerte des unteren 16-Bit-Wortes durchlaufen, nur die Low-Wort-Rekurrenz simuliert und die Übertragsreste modulo \(4\) mit den durch das Zielwort erzwungenen Differenzen verglichen.
Für jedes überlebende Low-Wort berechnet die Implementierung anschließend die exakten Überträge neu und testet die arithmetische Progression \(t_0+52r\) möglicher High-Wörter. Jedes erfolgreiche Paar aus High- und Low-Wort wird zu einem 48-Bit-Startzustand zusammengesetzt; doppelte Zustände werden nach dem Sortieren entfernt.
Nachdem beide Zielwörter in ihre eindeutigen Startzustände umgewandelt wurden, transformiert die Implementierung diese in ungerade Reste modulo \(2^{48}\), berechnet ein modulares Inverses und löst den Exponenten in der Untergruppe der Ordnung \(2^{46}\) Bit für Bit. Danach werden die vier möglichen Anhebungen mit schnellen affinen Sprüngen überprüft, was erheblich billiger ist als das schrittweise Durchlaufen des Generators.
Die sprachspezifischen Arithmetikdetails unterscheiden sich leicht. C++ benutzt ein 128-Bit-Zwischenprodukt und maskiert anschließend zurück auf \(48\) Bit. Python verwendet beliebig große Ganzzahlen mit derselben Maskierungsregel. Java vermeidet Überläufe in signierter 64-Bit-Arithmetik, indem jeder 48-Bit-Faktor in zwei 24-Bit-Hälften zerlegt und die Teilprodukte vor dem Maskieren wieder zusammengesetzt werden.
Sei \(m\) die Länge des Zielwortes und \(R\) die Anzahl der Start-Low-Wörter, die den Übertragsfilter überleben. Das Scannen der Low-Wörter kostet \(O(2^{16}m)\). Das erneute Berechnen der exakten Übertragsfolgen kostet \(O(Rm)\). Die Suche im High-Wort ist im pessimistischen Worst Case \(O\!\left(R\left\lceil\frac{2^{32}}{52}\right\rceil m\right)\), weil jedes überlebende Low-Wort mit einer arithmetischen Progression möglicher 32-Bit-High-Wörter gepaart wird.
In der Praxis sind die Übertragsbedingungen jedoch extrem restriktiv, sodass \(R\) für die festen Wörter dieser Aufgabe sehr klein ist und die Rekonstruktionsphase von der anfänglichen \(2^{16}\)-Suche dominiert wird. Die Distanzphase benötigt nur \(O(\log 2^{48})\) modulare Multiplikationen sowie höchstens vier Verifikationen per affinem Sprung. Der Speicherbedarf ist \(O(R+m)\) und damit für die gegebenen Eingaben effektiv konstant.
Verilen üreteç, durumu
$$a_{n+1}=A a_n + C \pmod{2^{48}},\qquad A=25214903917,\quad C=11$$
bağıntısıyla güncellenen 48 bitlik bir lineer kongrüans üretecidir. Her durumda üst \(32\) bit alınır, modulo \(52\) uygulanır ve \(0,\dots,25\) aralığı a ile z'ye, \(26,\dots,51\) aralığı ise A ile Z'ye çevrilir. Soru, dizide geçen iki hedef kelime arasındaki tam adım farkını istemektedir. Çevrim uzunluğu \(2^{48}\) olduğu için doğrudan simülasyon pratik değildir; bunun yerine çözüm önce her hedef kelimenin tekil başlangıç durumunu geri kurar, ardından aradaki mesafeyi cebirsel olarak hesaplar.
\(n\) anında üretilen kodu
$$u_n=\left\lfloor\frac{a_n}{2^{16}}\right\rfloor \bmod 52$$
ile gösterelim. Kod dizisi \(t_0,t_1,\dots,t_{m-1}\) olan bir hedef kelime için amaç,
$$u_i=t_i\qquad (0 \le i \lt m)$$
koşulunu sağlayan bütün başlangıç durumlarını bulmaktır.
Her durumu
$$a_n=2^{16}q_n+\ell_n,\qquad 0\le \ell_n \lt 2^{16},\qquad 0\le q_n \lt 2^{32}$$
şeklinde yazalım. Bu ayrım yapıldığında dinamik, alt \(16\) bitlik kısım ile üst \(32\) bitlik kısım olarak doğal biçimde ikiye bölünür. Alt kelime için
$$\ell_{n+1}\equiv A\ell_n+C \pmod{2^{16}}$$
bağıntısı vardır ve üst kelimeye taşınan değer
$$\kappa_n=\left\lfloor\frac{A\ell_n+C}{2^{16}}\right\rfloor$$
olarak tanımlanır. Böylece üst kelime
$$q_{n+1}\equiv A q_n+\kappa_n \pmod{2^{32}}$$
bağıntısını sağlar. Çıktı şartı ise yalnızca \(q_n\)'ye bağlıdır:
$$q_n\equiv t_n \pmod{52}.$$
Yöntemin ana fikri budur: tüm taşıma dizisi başlangıçtaki alt kelime \(\ell_0\) tarafından belirlenir; başlangıç üst kelimesi \(q_0\) ise sadece modulo \(2^{32}\) lineer bir yinelemeyi tutturmak zorundadır.
Uygulama önce çok ucuz bir gerekli koşul kullanır. Çünkü \(A\equiv 1 \pmod 4\), üst kelime yinelemesini modulo \(4\)'e indirince
$$q_{n+1}-q_n\equiv \kappa_n \pmod 4$$
elde edilir. \(q_n\equiv t_n \pmod{52}\) olduğundan buradan
$$\kappa_n\equiv t_{n+1}-t_n \pmod 4$$
sonucu çıkar. Yani hedef kelimedeki her komşu karakter çifti, taşımanın modulo \(4\) kalıntısını zorlar. Başlangıç alt kelimesi \(\ell_0\) yalnızca \(2^{16}\) farklı değer alabilir ve her biri için alt kelime yinelemesi deterministik bir taşıma dizisi üretir. Bu kalıntılar hedefin zorladığı koşullardan birini bile sağlamıyorsa aday hemen elenir.
Böylece ilk aşama, tüm \(2^{48}\) durum uzayını taramak yerine yalnızca \(65536\) adayın tam taramasına dönüşür.
Bir başlangıç alt kelimesi modulo-\(4\) filtresini geçtiğinde, artık tam taşıma değerleri \(\kappa_0,\kappa_1,\dots,\kappa_{m-2}\) bilinir. Başlangıç üst kelimesi şu koşulu sağlamalıdır:
$$q_0\equiv t_0 \pmod{52}.$$
Bu yüzden
$$q_0=t_0+52r,\qquad 0\le q_0 \lt 2^{32}$$
yazabiliriz. Her böyle aday için
$$q_{i+1}\equiv A q_i+\kappa_i \pmod{2^{32}}$$
bağıntısı yürütülür ve her adımda \(q_i\equiv t_i \pmod{52}\) koşulu denetlenir. Başarılı her \(q_0\) değeri, tam başlangıç durumunu
$$a_0=2^{16}q_0+\ell_0$$
olarak verir. Problemin gerçek iki hedef kelimesi için bu süreç her kelime adına tam bir geçerli başlangıç durumu üretir.
Tek adımlık geçiş affine yapıdadır: \(x\mapsto A x+C\). Affine dönüşümlerin bileşkesi yine affine olduğundan, her \(s\ge 0\) için
$$a_{n+s}=\alpha_s a_n+\beta_s \pmod{2^{48}}$$
şeklinde katsayılar vardır. İki affine dönüşüm sırasıyla \(x\mapsto \alpha_1 x+\beta_1\) ve \(x\mapsto \alpha_2 x+\beta_2\) ise bileşkeleri
$$x\mapsto \alpha_1\alpha_2 x+(\alpha_1\beta_2+\beta_1)$$
olur. Bu nedenle ikili üs alma, sıradan modüler üs almada olduğu gibi burada da çalışır; tekrarlı karesini alma ile \((\alpha_s,\beta_s)\) çifti \(O(\log s)\) sürede elde edilir. Uygulama bunu hem doğrulama için hem de ayrık log adımından sonra geriye kalan birkaç mesafe adayını test etmek için kullanır.
Şu dönüştürülmüş büyüklüğü tanımlayalım:
$$b_n=(A-1)a_n+C \pmod{2^{48}}.$$
O zaman
$$\begin{aligned} b_{n+1} &=(A-1)(A a_n+C)+C\\ &=A\bigl((A-1)a_n+C\bigr)\\ &\equiv A b_n \pmod{2^{48}} \end{aligned}$$
olur. Böylece affine yineleme saf çarpımsal bir yinelemeye indirgenir. Cebirsel kırılma noktası tam olarak budur.
Ayrıca her \(b_n\) tektir. Çünkü \(A-1\) sayısı \(4\)'e bölünür, \(C=11\) ise tektir; dolayısıyla \((A-1)a_n+C\equiv 3 \pmod 4\). Bu yüzden \(b_n\), modulo \(2^{48}\) altında terslenebilir.
\(s\) ve \(t\) iki geri kurulmuş başlangıç durumu olsun; \(t\), \(s\)'den \(\Delta\) adım sonra gelsin. O zaman
$$b_t\equiv A^{\Delta} b_s \pmod{2^{48}}$$
ve dolayısıyla
$$A^{\Delta}\equiv b_t\,b_s^{-1}\pmod{2^{48}}$$
elde edilir. Sağ taraftaki oran \(1 \pmod 4\) kalıntısına sahiptir; bu nedenle \(A\) tarafından üretilen ilgili çevrimsel \(2\)-kuvvet alt grubunda bulunur.
\(2^{48}\) modunda, yukarıdaki alt grup içinde çarpan \(A\)'nın mertebesi \(2^{46}\)'dır. Bu yüzden üs \(\Delta\), ilk aşamada yalnızca \(2^{46}\) modunda belirlenir.
Uygulama bu üssü bit bit çıkarır. Mevcut oran \(A^e\) ise, bunu \(2^{45-i}\) kuvvetine yükseltmek \(e\)'nin \(i\). bitinin sıfır mı bir mi olduğunu söyler: sonuç \(1\) değilse o bit mutlaka \(1\)'dir ve sıradaki bite geçmeden önce ilgili \(A^{2^i}\) çarpanı kaldırılır. Böylece temel çözüm
$$\Delta\equiv \Delta_0 \pmod{2^{46}}$$
elde edilir. Ancak \(a\mapsto (A-1)a+C\) dönüşümü \(2^{48}\) modunda birebir değildir; çünkü \(\gcd(A-1,2^{48})=4\). Yani dönüştürülmüş dizi, aynı anda dört LCG durumunu özdeşleştirir. Bu nedenle gerçek mesafe şu dört olasılıktan biridir:
$$\Delta_0,\qquad \Delta_0+2^{46},\qquad \Delta_0+2\cdot 2^{46},\qquad \Delta_0+3\cdot 2^{46}.$$
Adım 4'teki affine sıçrama formülü bu dört yükseltmeyi doğrudan sınar ve tam adım sayısını seçer.
Uzunluğu \(2\) olan ve kodları \(t_0\) ile \(t_1\) olan bir hedef önek alalım. Başlangıç alt kelimesi \(\ell_0\),
$$\kappa_0=\left\lfloor\frac{A\ell_0+C}{2^{16}}\right\rfloor$$
taşımasını üretir. Bu alt kelimenin işe yarayabilmesi için gerekli koşul
$$\kappa_0\equiv t_1-t_0 \pmod 4$$
eşitliğidir. \(2^{16}\) adayın çoğu daha burada elenir. Ayakta kalan her aday için üst kelime
$$q_0=t_0+52r$$
aritmetik progresyonu üzerinde olmalıdır. Bu adayların tam 32 bitlik yineleme ile test edilmesi, ya hepsini reddeder ya da gerçek başlangıç durumunu verir. Daha uzun öneklerde aynı mantık, tüm taşıma dizisi boyunca tekrarlanır.
C++, Python ve Java uygulamaları aynı matematiksel iş akışını izler. Önce harfler \(0\) ile \(51\) arasındaki sayılara dönüştürülür. Sonra tüm \(2^{16}\) olası alt \(16\) bit başlangıç değeri dolaşılır; yalnızca alt kelime yinelemesi simüle edilir ve taşıma kalıntıları modulo \(4\), hedef kelimenin komşu karakter farklarıyla karşılaştırılır.
Hayatta kalan her alt kelime adayı için uygulama tam taşıma dizisini yeniden hesaplar ve olası üst kelimelerin aritmetik progresyonu \(t_0+52r\) üzerinde gezinir. Başarılı her üst-alt kelime çifti tek bir 48 bitlik başlangıç durumuna birleştirilir; tekrar eden durumlar sıralama sonrasında ayıklanır.
İki hedef kelime de tekil başlangıç durumlarına indirgendikten sonra uygulama bunları modulo \(2^{48}\) altında tek kalıntılara dönüştürür, modüler ters alır ve \(2^{46}\) mertebeli alt gruptaki üssü bit bit çözer. Elde edilen temel mesafe daha sonra dört olası yükseltme ile sınanır; bu sınama, affine hızlı sıçrama sayesinde adım adım yürütmeden çok daha ucuzdur.
Düşük seviyeli aritmetik ayrıntıları dilden dile biraz değişir. C++ sürümü 128 bitlik ara çarpım kullanıp sonucu \(48\) bite maskeler. Python aynı maskeyle sınırsız büyüklükte tam sayılar kullanır. Java ise işaretli 64 bit çarpım taşmasını önlemek için her 48 bitlik çarpanı iki adet 24 bitlik parçaya ayırır, kısmi çarpımları birleştirir ve ardından maskeyi uygular.
\(m\) hedef kelime uzunluğu, \(R\) ise taşıma filtresini geçen başlangıç alt kelime sayısı olsun. Alt kelime taraması \(O(2^{16}m)\) maliyetlidir. Tam taşıma dizilerini yeniden kurmak \(O(Rm)\) zaman alır. Üst kelime araması, kötümser en kötü durumda her hayatta kalan alt kelimeyi olası 32 bitlik üst kelimelerin aritmetik progresyonuyla eşleştirdiği için \(O\!\left(R\left\lceil\frac{2^{32}}{52}\right\rceil m\right)\) olur.
Pratikte taşıma koşulları son derece seçicidir; bu yüzden problemin sabit hedef kelimeleri için \(R\) çok küçüktür ve geri kurma aşaması büyük ölçüde ilk \(2^{16}\) taraması tarafından belirlenir. Mesafe aşaması yalnızca \(O(\log 2^{48})\) adet modüler çarpım ve en fazla dört affine sıçrama doğrulaması gerektirir. Bellek kullanımı \(O(R+m)\) düzeyindedir ve verilen girdi boyutlarında fiilen sabittir.
Se nos da un generador lineal congruencial de \(48\) bits con actualización de estado
$$a_{n+1}=A a_n + C \pmod{2^{48}},\qquad A=25214903917,\quad C=11.$$
Cada estado emite una letra de un alfabeto de \(52\) símbolos tomando los \(32\) bits altos, reduciéndolos módulo \(52\) y mapeando \(0,\dots,25\) a a hasta z y \(26,\dots,51\) a A hasta Z. El objetivo es hallar la distancia exacta, en pasos, entre las dos palabras objetivo que aparecen en la secuencia. Como el período del generador es \(2^{48}\), una simulación directa es inviable; la solución reconstruye primero el estado inicial único de cada palabra y después calcula la separación usando álgebra modular.
Sea
$$u_n=\left\lfloor\frac{a_n}{2^{16}}\right\rfloor \bmod 52$$
el código emitido en el instante \(n\). Para una palabra objetivo con códigos \(t_0,t_1,\dots,t_{m-1}\), buscamos todos los estados iniciales \(a_0\) que satisfacen
$$u_i=t_i\qquad (0 \le i \lt m).$$
Escribimos cada estado como
$$a_n=2^{16}q_n+\ell_n,\qquad 0\le \ell_n \lt 2^{16},\qquad 0\le q_n \lt 2^{32}.$$
Al sustituir en la recurrencia, la dinámica se separa de forma natural en una parte baja de \(16\) bits y una parte alta de \(32\) bits. La palabra baja evoluciona según
$$\ell_{n+1}\equiv A\ell_n+C \pmod{2^{16}},$$
y el acarreo que sube a la parte alta es
$$\kappa_n=\left\lfloor\frac{A\ell_n+C}{2^{16}}\right\rfloor.$$
Por tanto, la palabra alta cumple
$$q_{n+1}\equiv A q_n+\kappa_n \pmod{2^{32}}.$$
La condición de salida depende solo de \(q_n\):
$$q_n\equiv t_n \pmod{52}.$$
Esta descomposición es la observación decisiva: toda la secuencia de acarreos queda determinada por la palabra baja inicial \(\ell_0\), mientras que la palabra alta inicial \(q_0\) solo debe ajustarse a una recurrencia lineal módulo \(2^{32}\).
La implementación aprovecha primero una condición necesaria muy barata. Como \(A\equiv 1 \pmod 4\), al reducir la recurrencia de la palabra alta módulo \(4\) obtenemos
$$q_{n+1}-q_n\equiv \kappa_n \pmod 4.$$
Dado que \(q_n\equiv t_n \pmod{52}\), se deduce
$$\kappa_n\equiv t_{n+1}-t_n \pmod 4.$$
Así, cada par de caracteres consecutivos de la palabra objetivo fija el residuo del acarreo módulo \(4\). La palabra baja inicial \(\ell_0\) solo puede tomar \(2^{16}\) valores, y para cada uno la recurrencia baja produce una secuencia de acarreos determinista. Si en algún punto ese patrón de residuos no coincide con el impuesto por la palabra, el candidato se descarta inmediatamente.
Eso reduce la primera fase a un barrido completo de solo \(65536\) candidatos, en lugar de explorar el espacio completo de \(2^{48}\) estados.
Cuando una palabra baja inicial supera el filtro módulo \(4\), ya conocemos los acarreos exactos \(\kappa_0,\kappa_1,\dots,\kappa_{m-2}\). La palabra alta inicial debe cumplir
$$q_0\equiv t_0 \pmod{52},$$
de modo que podemos escribir
$$q_0=t_0+52r,\qquad 0\le q_0 \lt 2^{32}.$$
Para cada candidato de esta progresión se itera
$$q_{i+1}\equiv A q_i+\kappa_i \pmod{2^{32}}$$
y se comprueba si sigue siendo cierto que \(q_i\equiv t_i \pmod{52}\) en todos los pasos. Cada valor válido de \(q_0\) produce un estado inicial completo
$$a_0=2^{16}q_0+\ell_0.$$
Para las dos palabras objetivo reales del problema, esta reconstrucción devuelve exactamente un estado inicial válido para cada palabra.
La transición de un paso es afín: \(x\mapsto A x+C\). La composición de transformaciones afines conserva esa forma, así que para todo entero no negativo \(s\) existen coeficientes \(\alpha_s\) y \(\beta_s\) tales que
$$a_{n+s}=\alpha_s a_n+\beta_s \pmod{2^{48}}.$$
Si dos transformaciones afines se escriben como \(x\mapsto \alpha_1 x+\beta_1\) y \(x\mapsto \alpha_2 x+\beta_2\), entonces su composición es
$$x\mapsto \alpha_1\alpha_2 x+(\alpha_1\beta_2+\beta_1).$$
Por ello, la exponenciación binaria funciona aquí igual que para las potencias modulares habituales: mediante cuadrados sucesivos se obtiene \((\alpha_s,\beta_s)\) en tiempo \(O(\log s)\). La implementación usa esta idea tanto para verificar como para probar los pocos candidatos de distancia que quedan tras resolver el logaritmo discreto.
Definimos la cantidad transformada
$$b_n=(A-1)a_n+C \pmod{2^{48}}.$$
Entonces
$$\begin{aligned} b_{n+1} &=(A-1)(A a_n+C)+C\\ &=A\bigl((A-1)a_n+C\bigr)\\ &\equiv A b_n \pmod{2^{48}}. \end{aligned}$$
La recurrencia afín se convierte así en una recurrencia puramente multiplicativa. Esa es la simplificación algebraica central.
Además, cada \(b_n\) es impar. En efecto, \(A-1\) es divisible por \(4\), mientras que \(C=11\) es impar, así que \((A-1)a_n+C\equiv 3 \pmod 4\). Por tanto, \(b_n\) siempre es invertible módulo \(2^{48}\).
Si \(s\) y \(t\) son los dos estados iniciales reconstruidos y \(t\) aparece \(\Delta\) pasos después de \(s\), entonces
$$b_t\equiv A^{\Delta} b_s \pmod{2^{48}},$$
y por consiguiente
$$A^{\Delta}\equiv b_t\,b_s^{-1}\pmod{2^{48}}.$$
La razón del lado derecho es congruente con \(1 \pmod 4\), así que pertenece al subgrupo cíclico relevante de potencia de \(2\) generado por \(A\).
Módulo \(2^{48}\), el multiplicador \(A\) tiene orden \(2^{46}\) dentro del subgrupo usado arriba. Por ello, el exponente \(\Delta\) solo queda determinado inicialmente módulo \(2^{46}\).
La implementación recupera ese exponente bit a bit. Si la razón actual vale \(A^e\), elevarla a \(2^{45-i}\) revela si el bit \(i\) de \(e\) es cero o uno: si el resultado no es \(1\), ese bit debe ser \(1\), y se divide el factor correspondiente \(A^{2^i}\) antes de continuar. De este modo se obtiene la solución base
$$\Delta\equiv \Delta_0 \pmod{2^{46}}.$$
Sin embargo, la aplicación \(a\mapsto (A-1)a+C\) no es inyectiva módulo \(2^{48}\): como \(\gcd(A-1,2^{48})=4\), la secuencia transformada identifica cuatro estados del LCG a la vez. Por eso la distancia real debe ser una de las cuatro cantidades
$$\Delta_0,\qquad \Delta_0+2^{46},\qquad \Delta_0+2\cdot 2^{46},\qquad \Delta_0+3\cdot 2^{46}.$$
La fórmula de salto afín del Paso 4 comprueba directamente estas cuatro elevaciones y selecciona el conteo exacto de pasos.
Tomemos un prefijo objetivo de longitud \(2\) con códigos \(t_0\) y \(t_1\). Una palabra baja inicial \(\ell_0\) produce el acarreo
$$\kappa_0=\left\lfloor\frac{A\ell_0+C}{2^{16}}\right\rfloor.$$
Una condición necesaria para que esa palabra baja pueda funcionar es
$$\kappa_0\equiv t_1-t_0 \pmod 4.$$
La mayoría de los \(2^{16}\) candidatos de palabra baja fracasan ya aquí. Para cada superviviente, la palabra alta debe pertenecer a la progresión aritmética
$$q_0=t_0+52r.$$
Probar estos candidatos con la recurrencia exacta de \(32\) bits los rechaza o produce un estado inicial auténtico. En palabras más largas, la misma lógica se repite a lo largo de toda la secuencia de acarreos.
Las implementaciones en C++, Python y Java siguen el mismo esquema matemático. Primero codifican las letras como números entre \(0\) y \(51\). Después enumeran los \(2^{16}\) posibles valores iniciales de los \(16\) bits bajos, simulan solo la recurrencia de esa parte baja y comparan los residuos de los acarreos módulo \(4\) con las diferencias impuestas por la palabra objetivo.
Para cada candidato de palabra baja que sobrevive, la implementación recalcula los acarreos exactos y recorre la progresión aritmética \(t_0+52r\) de posibles palabras altas. Cada pareja válida de palabra alta y palabra baja se ensambla en un estado inicial de \(48\) bits, y los duplicados se eliminan tras ordenar.
Una vez convertidas las dos palabras objetivo en sus estados iniciales únicos, la implementación las transforma en residuos impares módulo \(2^{48}\), calcula un inverso modular y resuelve el exponente dentro del subgrupo de orden \(2^{46}\) bit a bit. Después prueba las cuatro elevaciones posibles mediante saltos afines rápidos, mucho más baratos que avanzar el generador paso a paso.
Los detalles aritméticos de bajo nivel cambian ligeramente según el lenguaje. C++ utiliza un producto intermedio de \(128\) bits y luego enmascara de nuevo a \(48\) bits. Python usa enteros de precisión arbitraria con la misma máscara. Java evita el desbordamiento en aritmética con signo de \(64\) bits separando cada factor de \(48\) bits en dos mitades de \(24\) bits y recombinando los productos parciales antes de aplicar la máscara.
Sea \(m\) la longitud de la palabra objetivo y \(R\) el número de palabras bajas iniciales que sobreviven al filtro de acarreos. El barrido de palabras bajas cuesta \(O(2^{16}m)\). Recalcular las secuencias exactas de acarreo cuesta \(O(Rm)\). La búsqueda sobre la palabra alta es \(O\!\left(R\left\lceil\frac{2^{32}}{52}\right\rceil m\right)\) en el peor caso pesimista, porque cada palabra baja superviviente se combina con una progresión aritmética de posibles palabras altas de \(32\) bits.
En la práctica, las restricciones sobre los acarreos son extremadamente fuertes, por lo que \(R\) es muy pequeño para las palabras fijas de este problema, y la fase de reconstrucción queda dominada por el barrido inicial de \(2^{16}\) casos. La fase de distancia requiere solo \(O(\log 2^{48})\) multiplicaciones modulares y como mucho cuatro verificaciones por salto afín. El uso de memoria es \(O(R+m)\), que en estas entradas es esencialmente constante.
题目给出一个 \(48\) 位线性同余生成器，其状态更新公式为
$$a_{n+1}=A a_n + C \pmod{2^{48}},\qquad A=25214903917,\quad C=11.$$
每个状态会输出一个来自 \(52\) 个符号字母表的字符。做法是取状态的高 \(32\) 位，对 \(52\) 取模，再把 \(0,\dots,25\) 映射成 a 到 z，把 \(26,\dots,51\) 映射成 A 到 Z。题目要求的是序列中两个目标单词之间的精确步数差。由于整个发生器的周期是 \(2^{48}\)，不可能靠朴素模拟走完整个轨道，因此真正可行的办法是先把两个目标单词各自对应的唯一起始状态反推出，再用模运算和群结构把距离直接算出来。
记时刻 \(n\) 输出的代码为
$$u_n=\left\lfloor\frac{a_n}{2^{16}}\right\rfloor \bmod 52.$$
如果某个目标单词的编码是 \(t_0,t_1,\dots,t_{m-1}\)，那么我们要找的就是所有满足
$$u_i=t_i\qquad (0 \le i \lt m)$$
的初始状态 \(a_0\)。
把每个状态写成
$$a_n=2^{16}q_n+\ell_n,\qquad 0\le \ell_n \lt 2^{16},\qquad 0\le q_n \lt 2^{32}.$$
把这个形式代入递推式以后，状态演化会自然分成低 \(16\) 位和高 \(32\) 位两部分。低位部分满足
$$\ell_{n+1}\equiv A\ell_n+C \pmod{2^{16}},$$
而向高位传递的进位是
$$\kappa_n=\left\lfloor\frac{A\ell_n+C}{2^{16}}\right\rfloor.$$
于是高位部分满足
$$q_{n+1}\equiv A q_n+\kappa_n \pmod{2^{32}}.$$
输出条件只和 \(q_n\) 有关：
$$q_n\equiv t_n \pmod{52}.$$
这是整道题最关键的拆分。原因在于：一旦起始低位 \(\ell_0\) 确定，整条进位序列 \(\kappa_0,\kappa_1,\dots\) 就完全确定了；而起始高位 \(q_0\) 只需要去满足一个模 \(2^{32}\) 的线性递推关系即可。
实现时先利用一个几乎不要成本的必要条件。因为 \(A\equiv 1 \pmod 4\)，把高位递推式对 \(4\) 取模，就得到
$$q_{n+1}-q_n\equiv \kappa_n \pmod 4.$$
又由于 \(q_n\equiv t_n \pmod{52}\)，所以必然有
$$\kappa_n\equiv t_{n+1}-t_n \pmod 4.$$
也就是说，目标单词中每一对相邻字符都会规定一个进位模 \(4\) 的剩余类。起始低位 \(\ell_0\) 只有 \(2^{16}\) 种可能，而对每一个候选值，低位递推都会生成一条确定的进位序列。如果这条序列在任何一步的模 \(4\) 结果和目标要求不一致，这个候选值就可以立刻排除。
于是第一阶段只需要完整扫描 \(65536\) 个低位起点，而不必碰整个 \(2^{48}\) 的状态空间。
一旦某个起始低位通过了模 \(4\) 的进位筛选，精确的进位 \(\kappa_0,\kappa_1,\dots,\kappa_{m-2}\) 就全部已知了。此时起始高位必须满足
$$q_0\equiv t_0 \pmod{52},$$
因此可以写成
$$q_0=t_0+52r,\qquad 0\le q_0 \lt 2^{32}.$$
对这个算术级数上的每个候选值，都去迭代
$$q_{i+1}\equiv A q_i+\kappa_i \pmod{2^{32}}$$
并检查每一步是否仍然满足 \(q_i\equiv t_i \pmod{52}\)。每个成功的 \(q_0\) 都会给出一个完整的起始状态
$$a_0=2^{16}q_0+\ell_0.$$
对于题目里真正需要的两个目标单词，这一阶段最后各自只剩下一个合法起始状态。
单步转移本身是一个仿射变换：\(x\mapsto A x+C\)。仿射变换做复合以后仍然是仿射变换，所以对任意非负整数 \(s\)，都存在系数 \(\alpha_s\) 和 \(\beta_s\)，使得
$$a_{n+s}=\alpha_s a_n+\beta_s \pmod{2^{48}}.$$
如果两个仿射变换分别写成 \(x\mapsto \alpha_1 x+\beta_1\) 与 \(x\mapsto \alpha_2 x+\beta_2\)，那么它们的复合就是
$$x\mapsto \alpha_1\alpha_2 x+(\alpha_1\beta_2+\beta_1).$$
这意味着可以像处理普通模幂一样，用二进制快速幂去计算多步跳转。通过不断平方，我们可以在 \(O(\log s)\) 时间内得到 \((\alpha_s,\beta_s)\)。实现中，后面验证候选距离时正是靠这个公式完成的，而不是一位一位地向前推进。
定义一个新的量
$$b_n=(A-1)a_n+C \pmod{2^{48}}.$$
则有
$$\begin{aligned} b_{n+1} &=(A-1)(A a_n+C)+C\\ &=A\bigl((A-1)a_n+C\bigr)\\ &\equiv A b_n \pmod{2^{48}}. \end{aligned}$$
这样一来，原本带常数项的仿射递推就被改写成了纯粹的乘法递推。这一步是整个解法里最重要的代数化简。
同时，每个 \(b_n\) 都一定是奇数。因为 \(A-1\) 被 \(4\) 整除，而 \(C=11\) 是奇数，所以 \((A-1)a_n+C\equiv 3 \pmod 4\)。因此 \(b_n\) 在模 \(2^{48}\) 意义下总是可逆的。
设两个目标单词对应的起始状态分别为 \(s\) 与 \(t\)，并且 \(t\) 恰好在 \(s\) 之后 \(\Delta\) 步出现，那么
$$b_t\equiv A^{\Delta} b_s \pmod{2^{48}},$$
于是
$$A^{\Delta}\equiv b_t\,b_s^{-1}\pmod{2^{48}}.$$
右边这个比值同余于 \(1 \pmod 4\)，因此它落在由 \(A\) 生成的那个相关循环 \(2\)-幂子群中。
在模 \(2^{48}\) 的环境下，前面这个子群里 \(A\) 的阶是 \(2^{46}\)。因此，指数 \(\Delta\) 一开始只能确定到模 \(2^{46}\)。
实现中采用逐位恢复指数的方法。假设当前比值等于 \(A^e\)，那么把它提升到 \(2^{45-i}\) 次方，就可以判断 \(e\) 的第 \(i\) 个二进制位是 \(0\) 还是 \(1\)：如果结果不是 \(1\)，那这一位必须是 \(1\)，随后就把相应的因子 \(A^{2^i}\) 消掉，再继续看下一位。这样可以得到一个基准解
$$\Delta\equiv \Delta_0 \pmod{2^{46}}.$$
但是映射 \(a\mapsto (A-1)a+C\) 在模 \(2^{48}\) 下并不是单射，因为 \(\gcd(A-1,2^{48})=4\)。也就是说，变换后的序列会把四个不同的 LCG 状态压缩到同一个等价类里。因此真实距离只能是下面四个值之一：
$$\Delta_0,\qquad \Delta_0+2^{46},\qquad \Delta_0+2\cdot 2^{46},\qquad \Delta_0+3\cdot 2^{46}.$$
最后利用步骤 4 的仿射跳转公式，直接验证这四个候选值，选出真正正确的步数。
假设目标前缀长度只有 \(2\)，它的编码是 \(t_0\) 和 \(t_1\)。某个起始低位 \(\ell_0\) 会产生进位
$$\kappa_0=\left\lfloor\frac{A\ell_0+C}{2^{16}}\right\rfloor.$$
这个低位候选值想要成立，至少必须满足
$$\kappa_0\equiv t_1-t_0 \pmod 4.$$
于是 \(2^{16}\) 个低位候选里绝大多数都会在这里被立刻删掉。对于每个存活下来的低位，高位起点必须落在算术级数
$$q_0=t_0+52r$$
上。再用精确的 \(32\) 位递推去测试这些候选值，要么全部失败，要么得到真正的起始状态。更长的单词只不过是在整条进位序列上重复同一套逻辑。
C++、Python 和 Java 三个实现遵循的是同一条数学路线。第一步都是把字母编码成 \(0\) 到 \(51\) 之间的整数。然后枚举全部 \(2^{16}\) 个低 \(16\) 位起点，只模拟低位递推，并把进位的模 \(4\) 结果与目标单词相邻字符差所规定的模式进行比较。
对于每个通过筛选的低位候选，实现会重新计算精确进位序列，再遍历可能高位起点形成的算术级数 \(t_0+52r\)。每个成功的高位与低位组合都会拼成一个 \(48\) 位起始状态，排序后再去重。
当两个目标单词都被还原成各自唯一的起始状态以后，实现会把它们转换成模 \(2^{48}\) 下的奇数剩余类，求一个模逆，然后在阶为 \(2^{46}\) 的子群中逐位求出指数。接着再把得到的基准距离提升成四个可能值，并用快速仿射跳转逐一验证。这样做远比真的把发生器向前跑上巨量步数要便宜得多。
三个语言版本只在底层算术细节上略有不同。C++ 版本使用 \(128\) 位中间乘积，再把结果掩码回 \(48\) 位。Python 版本依赖任意精度整数，然后应用相同的掩码规则。Java 版本为了避免有符号 \(64\) 位乘法溢出，把每个 \(48\) 位因子拆成两个 \(24\) 位部分，先算部分积，再重新组合并掩码。
设目标单词长度为 \(m\)，通过进位筛选的起始低位个数为 \(R\)。低位扫描成本是 \(O(2^{16}m)\)。重新计算精确进位序列需要 \(O(Rm)\)。高位搜索在悲观最坏情况下是 \(O\!\left(R\left\lceil\frac{2^{32}}{52}\right\rceil m\right)\)，因为每个保留下来的低位都要和一整条 \(32\) 位高位候选的算术级数配对测试。
但在实际输入里，进位条件非常苛刻，所以 \(R\) 极小，重建阶段几乎完全由最开始的 \(2^{16}\) 次低位扫描主导。距离计算阶段只需要 \(O(\log 2^{48})\) 次模乘以及最多四次仿射跳转验证。内存使用量为 \(O(R+m)\)，对本题的固定规模来说基本可以视为常数。
В задаче дан 48-битный линейный конгруэнтный генератор со схемой обновления
$$a_{n+1}=A a_n + C \pmod{2^{48}},\qquad A=25214903917,\quad C=11.$$
Каждое состояние порождает один символ из алфавита из \(52\) знаков: берутся верхние \(32\) бита, затем вычисляется остаток по модулю \(52\), после чего \(0,\dots,25\) соответствуют a–z, а \(26,\dots,51\) соответствуют A–Z. Требуется найти точное число шагов между двумя целевыми словами, появляющимися в этой последовательности. Поскольку период генератора равен \(2^{48}\), прямое моделирование невозможно; поэтому решение сначала восстанавливает уникальное начальное состояние для каждого слова, а затем вычисляет расстояние между ними чисто алгебраически.
Обозначим код, выдаваемый в момент \(n\), через
$$u_n=\left\lfloor\frac{a_n}{2^{16}}\right\rfloor \bmod 52.$$
Если целевое слово кодируется последовательностью \(t_0,t_1,\dots,t_{m-1}\), то нужно найти все начальные состояния \(a_0\), для которых
$$u_i=t_i\qquad (0 \le i \lt m).$$
Представим состояние в виде
$$a_n=2^{16}q_n+\ell_n,\qquad 0\le \ell_n \lt 2^{16},\qquad 0\le q_n \lt 2^{32}.$$
После подстановки в рекуррентную формулу динамика естественно распадается на младшую 16-битную и старшую 32-битную части. Для младшего слова получаем
$$\ell_{n+1}\equiv A\ell_n+C \pmod{2^{16}},$$
а перенос в старшую часть равен
$$\kappa_n=\left\lfloor\frac{A\ell_n+C}{2^{16}}\right\rfloor.$$
Следовательно, старшее слово подчиняется соотношению
$$q_{n+1}\equiv A q_n+\kappa_n \pmod{2^{32}}.$$
Условие на вывод зависит только от \(q_n\):
$$q_n\equiv t_n \pmod{52}.$$
Это и есть ключевой структурный разрез задачи: вся последовательность переносов полностью определяется стартовым младшим словом \(\ell_0\), а стартовое старшее слово \(q_0\) должно лишь удовлетворить линейной рекурсии по модулю \(2^{32}\).
На первом этапе реализация использует очень дешевое необходимое условие. Поскольку \(A\equiv 1 \pmod 4\), редукция рекурсии для старшего слова по модулю \(4\) дает
$$q_{n+1}-q_n\equiv \kappa_n \pmod 4.$$
Из \(q_n\equiv t_n \pmod{52}\) следует
$$\kappa_n\equiv t_{n+1}-t_n \pmod 4.$$
То есть каждая пара соседних символов целевого слова жестко задает остаток переноса по модулю \(4\). У стартового младшего слова \(\ell_0\) всего \(2^{16}\) возможных значений, и для каждого из них младшая рекурсия порождает детерминированную последовательность переносов. Если хотя бы на одном шаге полученный остаток не совпадает с требуемым, кандидат немедленно отбрасывается.
Так первая фаза превращается в полный перебор лишь \(65536\) значений вместо исследования всего пространства из \(2^{48}\) состояний.
Как только стартовое младшее слово прошло фильтр по модулю \(4\), точные переносы \(\kappa_0,\kappa_1,\dots,\kappa_{m-2}\) уже известны. Стартовое старшее слово обязано удовлетворять условию
$$q_0\equiv t_0 \pmod{52},$$
поэтому его можно записать как
$$q_0=t_0+52r,\qquad 0\le q_0 \lt 2^{32}.$$
Для каждого такого кандидата итерируется
$$q_{i+1}\equiv A q_i+\kappa_i \pmod{2^{32}}$$
и проверяется, что на каждом шаге остается верным \(q_i\equiv t_i \pmod{52}\). Каждый успешный \(q_0\) дает полный стартовый 48-битный вектор состояния
$$a_0=2^{16}q_0+\ell_0.$$
Для двух реальных целевых слов из задачи эта процедура оставляет ровно по одному допустимому начальному состоянию.
Переход за один шаг аффинен: \(x\mapsto A x+C\). Композиция аффинных преобразований снова аффинна, поэтому для любого неотрицательного \(s\) существуют коэффициенты \(\alpha_s\) и \(\beta_s\), такие что
$$a_{n+s}=\alpha_s a_n+\beta_s \pmod{2^{48}}.$$
Если два аффинных преобразования записаны как \(x\mapsto \alpha_1 x+\beta_1\) и \(x\mapsto \alpha_2 x+\beta_2\), то их композиция имеет вид
$$x\mapsto \alpha_1\alpha_2 x+(\alpha_1\beta_2+\beta_1).$$
Значит, двоичное возведение в степень работает здесь точно так же, как и для обычных модульных степеней: повторным возведением в квадрат можно получить \((\alpha_s,\beta_s)\) за \(O(\log s)\). Именно это используется при проверке немногих кандидатов на расстояние, оставшихся после этапа дискретного логарифма.
Введем новую величину
$$b_n=(A-1)a_n+C \pmod{2^{48}}.$$
Тогда
$$\begin{aligned} b_{n+1} &=(A-1)(A a_n+C)+C\\ &=A\bigl((A-1)a_n+C\bigr)\\ &\equiv A b_n \pmod{2^{48}}. \end{aligned}$$
То есть исходная аффинная рекурсия превращается в чисто мультипликативную. Это и есть главное алгебраическое упрощение.
Кроме того, каждое \(b_n\) нечетно. Действительно, число \(A-1\) делится на \(4\), а \(C=11\) нечетно, поэтому \((A-1)a_n+C\equiv 3 \pmod 4\). Следовательно, \(b_n\) всегда обратимо по модулю \(2^{48}\).
Если \(s\) и \(t\) — два восстановленных стартовых состояния, а слово \(t\) возникает через \(\Delta\) шагов после \(s\), то
$$b_t\equiv A^{\Delta} b_s \pmod{2^{48}},$$
откуда
$$A^{\Delta}\equiv b_t\,b_s^{-1}\pmod{2^{48}}.$$
Правая часть сравнима с \(1 \pmod 4\), а значит лежит в нужной циклической \(2\)-степенной подгруппе, порожденной \(A\).
По модулю \(2^{48}\) множитель \(A\) имеет порядок \(2^{46}\) внутри рассматриваемой подгруппы. Поэтому показатель \(\Delta\) сначала определяется только по модулю \(2^{46}\).
Реализация восстанавливает этот показатель бит за битом. Если текущее отношение равно \(A^e\), то возведение его в степень \(2^{45-i}\) показывает, равен ли \(i\)-й бит числа \(e\) нулю или единице: если результат не равен \(1\), то этот бит обязан быть равен \(1\), и соответствующий множитель \(A^{2^i}\) делится до перехода к следующему биту. Так получается базовое решение
$$\Delta\equiv \Delta_0 \pmod{2^{46}}.$$
Однако отображение \(a\mapsto (A-1)a+C\) не инъективно по модулю \(2^{48}\): поскольку \(\gcd(A-1,2^{48})=4\), преобразованная последовательность отождествляет сразу четыре состояния генератора. Значит, истинное расстояние обязано быть одним из четырех значений
$$\Delta_0,\qquad \Delta_0+2^{46},\qquad \Delta_0+2\cdot 2^{46},\qquad \Delta_0+3\cdot 2^{46}.$$
Формула быстрого аффинного прыжка из шага 4 напрямую проверяет эти четыре подъема и выбирает правильное число шагов.
Пусть целевой префикс имеет длину \(2\) и коды \(t_0\) и \(t_1\). Некоторое стартовое младшее слово \(\ell_0\) порождает перенос
$$\kappa_0=\left\lfloor\frac{A\ell_0+C}{2^{16}}\right\rfloor.$$
Необходимое условие работоспособности этого кандидата таково:
$$\kappa_0\equiv t_1-t_0 \pmod 4.$$
Большинство из \(2^{16}\) кандидатов отсеивается уже здесь. Для каждого выжившего младшего слова стартовое старшее слово должно лежать в арифметической прогрессии
$$q_0=t_0+52r.$$
Проверка этих значений через точную 32-битную рекурсию либо отвергает их, либо дает настоящий стартовый вектор состояния. Для более длинных слов та же логика повторяется вдоль всей последовательности переносов.
Реализации на C++, Python и Java используют один и тот же математический конвейер. Сначала буквы кодируются числами от \(0\) до \(51\). Затем перебираются все \(2^{16}\) возможных стартовых значения младших \(16\) бит, моделируется только младшая рекурсия и сравниваются остатки переносов по модулю \(4\) с разностями, которые навязывает целевое слово.
Для каждого прошедшего кандидата по младшему слову реализация заново вычисляет точные переносы и перебирает арифметическую прогрессию \(t_0+52r\) возможных старших слов. Каждая успешная пара старшей и младшей частей собирается в 48-битное стартовое состояние, после чего дубликаты удаляются сортировкой и фильтрацией.
Когда оба целевых слова преобразованы в свои уникальные стартовые состояния, реализация переводит их в нечетные вычеты по модулю \(2^{48}\), находит модульный обратный элемент и восстанавливает показатель в подгруппе порядка \(2^{46}\) по одному биту за раз. Затем она проверяет четыре возможных подъема этого показателя с помощью быстрых аффинных прыжков, что значительно дешевле, чем пошаговое продвижение генератора.
Низкоуровневые арифметические детали чуть различаются по языкам. В C++ используется 128-битное промежуточное произведение с последующим маскированием обратно к \(48\) битам. В Python применяются целые произвольной точности с тем же правилом маски. В Java переполнение знакового 64-битного произведения обходится разбиением каждого 48-битного множителя на две 24-битные части и последующим объединением частичных произведений перед маскированием.
Пусть \(m\) — длина целевого слова, а \(R\) — число стартовых младших слов, переживших фильтр по переносам. Сканирование младших слов стоит \(O(2^{16}m)\). Повторное вычисление точных последовательностей переносов требует \(O(Rm)\). Поиск по старшему слову в пессимистическом худшем случае имеет сложность \(O\!\left(R\left\lceil\frac{2^{32}}{52}\right\rceil m\right)\), так как каждому выжившему младшему слову соответствует арифметическая прогрессия возможных 32-битных старших слов.
На практике условия на переносы чрезвычайно жесткие, поэтому для фиксированных слов этой задачи \(R\) очень мало, и стадия восстановления фактически определяется начальным перебором \(2^{16}\) низких слов. Стадия вычисления расстояния требует лишь \(O(\log 2^{48})\) модульных умножений и не более четырех проверок с аффинным прыжком. Память равна \(O(R+m)\), что для данных размеров фактически является константой.
لدينا مولّد خطي توافقي بطول \(48\) بت، وتحديث حالته يتم وفق العلاقة
$$a_{n+1}=A a_n + C \pmod{2^{48}},\qquad A=25214903917,\quad C=11.$$
كل حالة تنتج حرفًا من أبجدية مكوّنة من \(52\) رمزًا، وذلك بأخذ أعلى \(32\) بت ثم الاختزال بترديد \(52\)، وبعدها تُحوَّل القيم \(0,\dots,25\) إلى a حتى z وتُحوَّل القيم \(26,\dots,51\) إلى A حتى Z. المطلوب هو حساب عدد الخطوات الدقيق بين الكلمتين الهدف داخل هذه السلسلة. وبما أن دورة المولّد طولها \(2^{48}\)، فإن المحاكاة المباشرة غير عملية؛ لذلك يعيد الحل أولًا بناء حالة البداية الوحيدة لكل كلمة، ثم يحسب المسافة بينهما باستخدام الجبر المعياري بدلًا من المشي خطوة بخطوة.
لنرمز إلى الشيفرة الصادرة عند اللحظة \(n\) بالرمز
$$u_n=\left\lfloor\frac{a_n}{2^{16}}\right\rfloor \bmod 52.$$
إذا كانت الكلمة الهدف تُشفَّر على الصورة \(t_0,t_1,\dots,t_{m-1}\)، فإننا نبحث عن جميع حالات البداية \(a_0\) التي تحقق
$$u_i=t_i\qquad (0 \le i \lt m).$$
نكتب كل حالة بالشكل
$$a_n=2^{16}q_n+\ell_n,\qquad 0\le \ell_n \lt 2^{16},\qquad 0\le q_n \lt 2^{32}.$$
وعند التعويض في علاقة التحديث تنفصل الحركة طبيعيًا إلى جزء سفلي من \(16\) بت وجزء علوي من \(32\) بت. فالجزء السفلي يحقق
$$\ell_{n+1}\equiv A\ell_n+C \pmod{2^{16}},$$
أما مقدار الحمل إلى الجزء العلوي فهو
$$\kappa_n=\left\lfloor\frac{A\ell_n+C}{2^{16}}\right\rfloor.$$
ومن ثم فإن الجزء العلوي يحقق
$$q_{n+1}\equiv A q_n+\kappa_n \pmod{2^{32}}.$$
شرط الخرج يعتمد فقط على \(q_n\):
$$q_n\equiv t_n \pmod{52}.$$
هذه هي الفكرة الأساسية في الحل: تسلسل الحمولات كله يتحدد من الجزء السفلي الابتدائي \(\ell_0\)، بينما الجزء العلوي الابتدائي \(q_0\) لا يحتاج إلا إلى مطابقة علاقة خطية بترديد \(2^{32}\).
تستفيد الخوارزمية أولًا من شرط لازم زهيد الكلفة. بما أن \(A\equiv 1 \pmod 4\)، فإن اختزال علاقة الجزء العلوي بترديد \(4\) يعطي
$$q_{n+1}-q_n\equiv \kappa_n \pmod 4.$$
ومع وجود \(q_n\equiv t_n \pmod{52}\) ينتج مباشرة
$$\kappa_n\equiv t_{n+1}-t_n \pmod 4.$$
أي إن كل زوج متجاور من الحروف في الكلمة الهدف يفرض بقايا محددة للحمل بترديد \(4\). والجزء السفلي الابتدائي \(\ell_0\) لا يملك إلا \(2^{16}\) احتمالًا، ولكل احتمال منها تنتج علاقة الجزء السفلي سلسلة حمولات محددة تمامًا. فإذا خالفت هذه البواقي شرطًا واحدًا فقط من الشروط المفروضة من الكلمة، يُرفض المرشح فورًا.
وبذلك تختزل المرحلة الأولى إلى فحص شامل لعدد \(65536\) من المرشحين بدلًا من التعامل مع فضاء الحالات الكامل ذي الحجم \(2^{48}\).
إذا اجتاز جزء سفلي ابتدائي ما مرشح الحمولات modulo \(4\)، فإن الحمولات الدقيقة \(\kappa_0,\kappa_1,\dots,\kappa_{m-2}\) تصبح معروفة بالكامل. وعندها يجب أن يحقق الجزء العلوي الابتدائي
$$q_0\equiv t_0 \pmod{52},$$
أي يمكن كتابته على صورة
$$q_0=t_0+52r,\qquad 0\le q_0 \lt 2^{32}.$$
ولكل قيمة مرشحة من هذه المتتالية الحسابية نكرر
$$q_{i+1}\equiv A q_i+\kappa_i \pmod{2^{32}}$$
ثم نتحقق من بقاء الشرط \(q_i\equiv t_i \pmod{52}\) صحيحًا في كل خطوة. وكل قيمة صحيحة لـ \(q_0\) تنتج حالة بداية كاملة
$$a_0=2^{16}q_0+\ell_0.$$
وبالنسبة إلى الكلمتين الفعليتين في المسألة، تنتهي هذه العملية إلى حالة بداية وحيدة صالحة لكل كلمة.
الانتقال بخطوة واحدة هو تحويل أفيني من الشكل \(x\mapsto A x+C\). وتركيب التحويلات الأفينية يبقى أفينيًا، لذلك لكل \(s\ge 0\) توجد معاملات \(\alpha_s\) و\(\beta_s\) تحقق
$$a_{n+s}=\alpha_s a_n+\beta_s \pmod{2^{48}}.$$
فإذا كُتب تحويلان أفينيان على الصورة \(x\mapsto \alpha_1 x+\beta_1\) و\(x\mapsto \alpha_2 x+\beta_2\)، فإن تركيبهما يساوي
$$x\mapsto \alpha_1\alpha_2 x+(\alpha_1\beta_2+\beta_1).$$
وهذا يعني أن الأس السريع الثنائي يعمل هنا كما يعمل في القوى المعيارية العادية: بالتربيع المتكرر يمكن الحصول على الزوج \((\alpha_s,\beta_s)\) في زمن \(O(\log s)\). ويستعمل التنفيذ هذه الفكرة في مرحلة التحقق النهائية بدل التقدم خطوة بخطوة عبر المولّد.
لنعرّف الكمية
$$b_n=(A-1)a_n+C \pmod{2^{48}}.$$
عندئذٍ
$$\begin{aligned} b_{n+1} &=(A-1)(A a_n+C)+C\\ &=A\bigl((A-1)a_n+C\bigr)\\ &\equiv A b_n \pmod{2^{48}}. \end{aligned}$$
وهكذا تتحول العلاقة التي كانت أفينية إلى علاقة ضرب محضة. وهذه هي القفزة الجبرية الأهم في الحل كله.
كذلك فإن كل \(b_n\) عدد فردي. والسبب أن \(A-1\) قابل للقسمة على \(4\)، في حين أن \(C=11\) فردي، ولذلك \((A-1)a_n+C\equiv 3 \pmod 4\). وعليه فإن \(b_n\) قابل للعكس معياريًا بترديد \(2^{48}\).
إذا كانت حالتا البداية المسترجعتان هما \(s\) و\(t\)، وكانت الكلمة الثانية تظهر بعد \(\Delta\) خطوة من الأولى، فإن
$$b_t\equiv A^{\Delta} b_s \pmod{2^{48}},$$
ومن ثم
$$A^{\Delta}\equiv b_t\,b_s^{-1}\pmod{2^{48}}.$$
والنسبة في الطرف الأيمن توافق \(1 \pmod 4\)، ولذلك تقع داخل الزمرة الدورية ذات رتبة من قوى \(2\) والمولَّدة بواسطة \(A\).
بترديد \(2^{48}\)، رتبة العنصر \(A\) في الزمرة المستعملة أعلاه هي \(2^{46}\). لذلك لا يتحدد الأس \(\Delta\) في البداية إلا modulo \(2^{46}\).
التنفيذ يستخرج هذا الأس بتًا بتًا. فإذا كانت النسبة الحالية تساوي \(A^e\)، فإن رفعها للقوة \(2^{45-i}\) يكشف ما إذا كان البت رقم \(i\) من \(e\) صفرًا أو واحدًا: فإذا لم تكن النتيجة \(1\)، فذلك يعني أن هذا البت يساوي \(1\)، وعندها يُزال العامل الموافق \(A^{2^i}\) قبل الانتقال إلى البت التالي. بهذه الطريقة نحصل على الحل الأساسي
$$\Delta\equiv \Delta_0 \pmod{2^{46}}.$$
لكن التحويل \(a\mapsto (A-1)a+C\) ليس تقابليًا modulo \(2^{48}\)، لأن \(\gcd(A-1,2^{48})=4\). أي إن السلسلة المحوَّلة تدمج أربع حالات مختلفة من حالات المولّد في فئة واحدة. ولذلك فإن المسافة الحقيقية لا بد أن تكون واحدة من القيم الأربع
$$\Delta_0,\qquad \Delta_0+2^{46},\qquad \Delta_0+2\cdot 2^{46},\qquad \Delta_0+3\cdot 2^{46}.$$
وصيغة القفز الأفيني في الخطوة 4 هي التي تختبر هذه الرفعات الأربع مباشرة وتختار عدد الخطوات الصحيح.
لنأخذ بادئة هدف طولها \(2\) ورمزاها \(t_0\) و\(t_1\). جزء سفلي ابتدائي \(\ell_0\) ينتج حملًا مساويًا لـ
$$\kappa_0=\left\lfloor\frac{A\ell_0+C}{2^{16}}\right\rfloor.$$
ولكي يكون هذا المرشح ممكنًا فلا بد من تحقق الشرط
$$\kappa_0\equiv t_1-t_0 \pmod 4.$$
ومعنى ذلك أن معظم المرشحين البالغ عددهم \(2^{16}\) يُستبعدون فورًا. أما كل مرشح ينجو من هذا الشرط، فإن جزأه العلوي الابتدائي يجب أن يقع على المتتالية الحسابية
$$q_0=t_0+52r.$$
ثم إن اختبار هذه القيم بواسطة العلاقة الدقيقة ذات \(32\) بت إما أن يرفضها أو يعطي حالة بداية حقيقية. وعند البوادئ الأطول تتكرر الفكرة نفسها على طول سلسلة الحمولات بأكملها.
تتبع تطبيقات C++ وPython وJava خط السير الرياضي نفسه. فهي تبدأ بترميز الحروف إلى أعداد من \(0\) إلى \(51\). ثم تعدّد كل قيم البداية الممكنة للـ \(16\) بت الدنيا، وعددها \(2^{16}\)، وتُحاكي فقط علاقة الجزء السفلي، ثم تقارن بواقي الحمولات modulo \(4\) مع الفروق التي تفرضها الحروف المتجاورة في الكلمة الهدف.
وبالنسبة إلى كل مرشح للجزء السفلي يبقى بعد التصفية، يعيد التنفيذ حساب الحمولات الدقيقة ثم يمرّ على المتتالية الحسابية \(t_0+52r\) الخاصة بالمرشحين الممكنين للجزء العلوي. وكل زوج صحيح من الجزأين العلوي والسفلي يُجمَّع في حالة بداية بطول \(48\) بت، ثم تزال التكرارات بعد الفرز.
وبعد تحويل الكلمتين الهدف إلى حالتي البداية الوحيدتين لهما، يحوّل التنفيذ هاتين الحالتين إلى بواقي فردية modulo \(2^{48}\)، ثم يحسب معكوسًا معياريًا، ويستخرج الأس داخل الزمرة ذات الرتبة \(2^{46}\) بتًا بتًا. بعد ذلك يجرّب الرفعات الأربع الممكنة لذلك الأس باستعمال قفزات أفينية سريعة، وهو أرخص بكثير من تكرار المولّد خطوة بعد خطوة.
التفاصيل الحسابية منخفضة المستوى تختلف قليلًا بين اللغات. فتنفيذ C++ يستخدم حاصل ضرب وسيطًا بطول \(128\) بت ثم يعيد اختزال النتيجة إلى \(48\) بت بالقناع. أما Python فيستعمل الأعداد الصحيحة غير المحدودة مع القناع نفسه. وأما Java فيتجنب فيض الضرب ذي \(64\) بت الموقّع عبر تقسيم كل عامل بطول \(48\) بت إلى نصفين بطول \(24\) بت ثم إعادة تركيب المجاميع الجزئية قبل تطبيق القناع.
لنفرض أن \(m\) هو طول الكلمة الهدف، وأن \(R\) هو عدد قيم البداية للجزء السفلي التي تنجو من مرشح الحمولات. مسح الجزء السفلي يكلف \(O(2^{16}m)\). وإعادة بناء سلاسل الحمولات الدقيقة تكلف \(O(Rm)\). أما البحث في الجزء العلوي ففي أسوأ تقدير متشائم يساوي \(O\!\left(R\left\lceil\frac{2^{32}}{52}\right\rceil m\right)\)، لأن كل مرشح ناجٍ للجزء السفلي يقترن بمتتالية حسابية من المرشحين ذوي \(32\) بت للجزء العلوي.
عمليًا، شروط الحمولات صارمة جدًا، ولذلك يكون \(R\) صغيرًا للغاية للكلمتين الثابتتين في هذه المسألة، فتغلب مرحلة المسح الأولية ذات \(2^{16}\) احتمالًا على زمن إعادة البناء كله. أما مرحلة حساب المسافة فتحتاج فقط إلى \(O(\log 2^{48})\) من عمليات الضرب المعياري وإلى ما لا يزيد على أربع عمليات تحقق بالقفز الأفيني. واستهلاك الذاكرة هو \(O(R+m)\)، وهو شبه ثابت لهذه المدخلات.