We seek the \(N\)-th XOR-prime among the integers below \(2^M\). The key reinterpretation is that an integer is not viewed with ordinary arithmetic, but as a polynomial over \(\mathbb F_2\): if
$$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$$
then it represents
$$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x].$$
An XOR-prime is therefore an integer whose associated polynomial is irreducible in \(\mathbb F_2[x]\). The implementations enumerate these objects in increasing integer order. The special even value \(2\), corresponding to the polynomial \(x\), is counted first; after that, every remaining XOR-prime is odd.
The solution is a sieve in the polynomial ring \(\mathbb F_2[x]\). Instead of ordinary multiplication with carries, it works with carryless multiplication, which matches polynomial multiplication with coefficients reduced modulo \(2\).
The map
$$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$$
turns the binary digits of \(n\) into polynomial coefficients. Under this encoding, bitwise XOR is simply polynomial addition in \(\mathbb F_2[x]\). If \(a\leftrightarrow A(x)\) and \(b\leftrightarrow B(x)\), then the XOR-product is
$$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j).$$
So a number is XOR-composite precisely when its polynomial factors nontrivially over \(\mathbb F_2\).
If \(n\) is even, then its least significant bit is \(0\), so the constant term of \(P_n(x)\) is \(0\). That means
$$P_n(x)=xQ(x)$$
for some polynomial \(Q(x)\). Therefore every even code larger than \(2\) is automatically XOR-composite. The only even XOR-prime is
$$2\leftrightarrow x,$$
which is irreducible because it has degree \(1\). This explains why the implementations count \(2\) immediately and then sieve only odd integers.
Let \(p\) be an odd XOR-prime, and let its binary length be \(\ell\). Then the associated polynomial has degree
$$\deg P_p=\ell-1.$$
Any odd XOR-composite that has \(p\) as a factor can be written as
$$P_n(x)=P_p(x)\,Q(x),$$
where \(Q(x)\) is another nonconstant polynomial with constant term \(1\). If \(Q\) has degree \(j\), then
$$\deg P_n=(\ell-1)+j.$$
Since the search is restricted to integers below \(2^M\), we need
$$\deg P_n\le M-1,$$
so the admissible cofactor degrees satisfy
$$j\le M-\ell.$$
The sieve marks every such product. Whatever odd code survives all these marking passes must be irreducible.
Fix a cofactor degree \(j\). Every monic polynomial of degree \(j\) has code
$$2^j\oplus t,\qquad 0\le t\lt 2^j,$$
because the top bit must be \(1\) and the lower \(j\) coefficients are free. So for one base polynomial \(p\), the values that must be marked are
$$p\otimes(2^j\oplus t),$$
with \(\otimes\) denoting carryless multiplication. There are exactly \(2^j\) such cofactors for this degree, and the implementations enumerate all of them.
Recomputing every carryless product from scratch would be too slow. Instead, the implementations traverse the lower part \(t\) in Gray-code order. Starting from \(g_0=0\), define
$$g_n=g_{n-1}\oplus \operatorname{lowbit}(n),$$
where \(\operatorname{lowbit}(n)\) is the least significant set bit of \(n\). This visits every value in \([0,2^j)\) exactly once, and consecutive values differ in only one bit. If the current cofactor changes by one bit \(2^r\), then the product changes by
$$p\otimes 2^r,$$
which is just a left shift of \(p\), because \(2^r\) represents the monomial \(x^r\). So each next marked value is obtained from the previous one with a single XOR against one shifted copy of the base code.
The sieve only needs cofactor degrees
$$j\ge \ell-1.$$
This is the polynomial analogue of starting the ordinary sieve of Eratosthenes at \(p^2\). If \(P_n=P_pQ\) with \(\deg Q\lt \deg P_p\), then \(Q\) has some irreducible factor of smaller degree than \(P_p\), so \(n\) will already be marked when that smaller-degree factor is processed. Beginning at equal degree therefore removes unnecessary work without losing any composite numbers.
The first few XOR-primes illustrate the idea:
$$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1.$$
Nearby odd integers can be XOR-composite for purely polynomial reasons. For example,
$$5\leftrightarrow x^2+1=(x+1)^2,$$
$$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$$
So \(5\) and \(9\) are removed by the sieve, while \(7\) survives. Listing all survivors in increasing order begins
$$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$$
Hence the \(10\)-th XOR-prime is \(41\), which is the small checkpoint matched by the implementations.
The C++, Python, and Java implementations allocate a mark table for all integers below \(2^M\) and initially treat every entry as a possible XOR-prime. They count \(2\) first, then scan only odd codes in increasing order. Whenever an odd code is still unmarked, the implementation has found the next XOR-prime and advances the running rank.
For each such survivor, the implementation computes its bit length, which gives the degree of the corresponding polynomial. It then loops over all admissible cofactor degrees \(j\). For each \(j\), it starts from the product with \(x^j\), which is just a left shift, and then walks through all monic degree-\(j\) cofactors in Gray-code order. Every generated product is marked as XOR-composite.
The crucial optimization is that consecutive cofactors differ by exactly one lower bit, so the next product is derived from the previous product with one XOR against a shifted copy of the base polynomial. The search stops immediately once the requested rank \(N\) has been reached.
The mark table has size \(2^M\), so memory usage is \(O(2^M)\). The outer scan over odd integers is also \(O(2^M)\). For a surviving XOR-prime of degree \(d\), the marking work is
$$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d.$$
A simple worst-case summary is therefore \(O(M2^M)\) time. In practice the constant factors are low, because the inner loop consists only of bit operations, and only surviving XOR-primes generate marking passes.
Gesucht ist die \(N\)-te XOR-Primzahl unterhalb von \(2^M\). Dabei werden die ganzen Zahlen nicht mit gewöhnlicher Arithmetik betrachtet, sondern als Polynome über \(\mathbb F_2\): Für
$$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$$
steht die Zahl für
$$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x].$$
Eine XOR-Primzahl ist also genau dann gegeben, wenn dieses Polynom in \(\mathbb F_2[x]\) irreduzibel ist. Die Implementierungen zählen diese Zahlen in aufsteigender Ganzzahlreihenfolge. Der besondere gerade Wert \(2\), also das Polynom \(x\), wird zuerst gezählt; danach ist jede weitere XOR-Primzahl ungerade.
Die Lösung verwendet ein Sieb im Polynomring \(\mathbb F_2[x]\). Anstelle der gewöhnlichen Multiplikation mit Überträgen benutzt sie die carryless-Multiplikation, also Polynom-Multiplikation mit Koeffizienten modulo \(2\).
Die Abbildung
$$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$$
macht aus den Binärziffern von \(n\) die Polynomkoeffizienten. Unter dieser Kodierung ist bitweises XOR genau die Addition in \(\mathbb F_2[x]\). Sind \(a\leftrightarrow A(x)\) und \(b\leftrightarrow B(x)\), dann lautet das XOR-Produkt
$$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j).$$
Damit ist eine Zahl genau dann XOR-zusammengesetzt, wenn ihr Polynom über \(\mathbb F_2\) nichttrivial faktorisiert.
Ist \(n\) gerade, dann ist das niederwertigste Bit \(0\), also hat \(P_n(x)\) konstanten Term \(0\). Folglich gilt
$$P_n(x)=xQ(x)$$
für ein geeignetes Polynom \(Q(x)\). Deshalb ist jeder gerade Code größer als \(2\) automatisch XOR-zusammengesetzt. Die einzige gerade XOR-Primzahl ist
$$2\leftrightarrow x,$$
denn \(x\) hat Grad \(1\) und ist daher irreduzibel. Genau deshalb zählen die Implementierungen zuerst \(2\) und sieben danach nur die ungeraden Zahlen.
Sei \(p\) eine ungerade XOR-Primzahl mit Binärlänge \(\ell\). Dann hat das zugehörige Polynom den Grad
$$\deg P_p=\ell-1.$$
Jede ungerade XOR-zusammengesetzte Zahl, die \(p\) als Faktor besitzt, hat die Form
$$P_n(x)=P_p(x)\,Q(x),$$
wobei \(Q(x)\) ein weiteres nichtkonstantes Polynom mit konstantem Term \(1\) ist. Hat \(Q\) den Grad \(j\), so gilt
$$\deg P_n=(\ell-1)+j.$$
Da nur Zahlen unterhalb von \(2^M\) betrachtet werden, muss
$$\deg P_n\le M-1$$
gelten, also
$$j\le M-\ell.$$
Das Sieb markiert alle diese Produkte. Jeder ungerade Code, der nach allen Markierungen übrig bleibt, muss daher irreduzibel sein.
Fixiere einen Kofaktorgrad \(j\). Jedes monische Polynom vom Grad \(j\) besitzt den Code
$$2^j\oplus t,\qquad 0\le t\lt 2^j,$$
denn das führende Bit muss \(1\) sein und die unteren \(j\) Koeffizienten sind frei. Für ein festes Basispolynom \(p\) müssen also genau die Werte
$$p\otimes(2^j\oplus t)$$
markiert werden, wobei \(\otimes\) die carryless-Multiplikation bezeichnet. Für diesen Grad gibt es genau \(2^j\) solche Kofaktoren, und die Implementierungen erzeugen sie vollständig.
Jedes carryless-Produkt neu auszurechnen wäre zu teuer. Deshalb durchlaufen die Implementierungen die unteren Teile \(t\) in Gray-Code-Reihenfolge. Ausgehend von \(g_0=0\) sei
$$g_n=g_{n-1}\oplus \operatorname{lowbit}(n),$$
wobei \(\operatorname{lowbit}(n)\) das niederwertigste gesetzte Bit von \(n\) bezeichnet. So wird jeder Wert in \([0,2^j)\) genau einmal besucht, und aufeinanderfolgende Werte unterscheiden sich nur in einem Bit. Ändert sich der Kofaktor um genau ein Bit \(2^r\), dann ändert sich auch das Produkt nur um
$$p\otimes 2^r,$$
und das ist bloß eine Linksverschiebung von \(p\), weil \(2^r\) dem Monom \(x^r\) entspricht. Der nächste markierte Wert entsteht also mit genau einem XOR gegen eine verschobene Kopie des Basiscodes.
Das Sieb braucht nur Kofaktorgrade
$$j\ge \ell-1.$$
Das ist das polynomielle Gegenstück dazu, beim klassischen Sieb erst bei \(p^2\) zu starten. Falls \(P_n=P_pQ\) mit \(\deg Q\lt \deg P_p\), dann besitzt \(Q\) einen irreduziblen Faktor kleineren Grades als \(P_p\), und \(n\) wäre bereits markiert worden, als dieser kleinere Faktor verarbeitet wurde. Der Start bei gleichem Grad spart also Arbeit, ohne irgendeine zusammengesetzte Zahl zu verlieren.
Die ersten XOR-Primzahlen sehen in Polynomschreibweise so aus:
$$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1.$$
Nahe liegende ungerade Zahlen können im XOR-Sinn zusammengesetzt sein, obwohl das mit gewöhnlicher Primzahltheorie nichts zu tun haben muss. Zum Beispiel gilt
$$5\leftrightarrow x^2+1=(x+1)^2,$$
$$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$$
Also werden \(5\) und \(9\) gestrichen, während \(7\) stehen bleibt. Die überlebenden Werte beginnen in aufsteigender Reihenfolge mit
$$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$$
Damit ist die \(10\)-te XOR-Primzahl gleich \(41\); genau diesen kleinen Kontrollwert treffen die Implementierungen.
Die C++-, Python- und Java-Implementierungen legen eine Markierungstabelle für alle Zahlen unterhalb von \(2^M\) an und behandeln zunächst jeden Eintrag als möglichen XOR-Primwert. Zuerst wird \(2\) gezählt, danach werden nur noch ungerade Codes in aufsteigender Reihenfolge betrachtet. Ist ein ungerader Code noch unmarkiert, wurde die nächste XOR-Primzahl gefunden und der laufende Rang erhöht.
Für jeden solchen Überlebenden bestimmt die Implementierung seine Bitlänge und damit den Grad des zugehörigen Polynoms. Anschließend werden alle zulässigen Kofaktorgrade \(j\) durchlaufen. Für jedes \(j\) beginnt die Erzeugung beim Produkt mit \(x^j\), also bei einer einfachen Linksverschiebung, und läuft dann in Gray-Code-Reihenfolge durch alle monischen Kofaktoren vom Grad \(j\). Jedes erzeugte Produkt wird als XOR-zusammengesetzt markiert.
Die entscheidende Optimierung ist, dass zwei aufeinanderfolgende Kofaktoren sich nur in einem unteren Bit unterscheiden. Darum lässt sich das nächste Produkt aus dem vorherigen mit genau einem XOR gegen eine verschobene Kopie des Basispolynoms gewinnen. Sobald der gewünschte Rang \(N\) erreicht ist, endet die Suche sofort.
Die Markierungstabelle hat Größe \(2^M\), also beträgt der Speicherbedarf \(O(2^M)\). Auch der äußere Durchlauf über die ungeraden Zahlen ist \(O(2^M)\). Für eine überlebende XOR-Primzahl vom Grad \(d\) ist die Markierungsarbeit
$$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d.$$
Eine einfache Worst-Case-Zusammenfassung ist daher \(O(M2^M)\) Zeit. Praktisch sind die Konstanten klein, weil die inneren Schritte nur aus Bitoperationen bestehen und Markierungsphasen nur für tatsächlich überlebende XOR-Primzahlen gestartet werden.
Aranan şey, \(2^M\)'den küçük sayılar arasında \(N\). XOR-primi bulmaktır. Buradaki kritik yorum şudur: sayılar normal aritmetikle değil, \(\mathbb F_2\) üzerindeki polinomlar olarak ele alınır. Eğer
$$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$$
ise karşılık gelen polinom
$$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x]$$
olur. Böylece XOR-prime olmak, ilgili polinomun \(\mathbb F_2[x]\) içinde indirgenemez olması demektir. Uygulamalar bu nesneleri artan tamsayı sırasıyla sayar. Özel çift değer \(2\), yani \(x\) polinomu, önce sayılır; ondan sonraki bütün XOR-prime değerler tektir.
Çözüm, \(\mathbb F_2[x]\) polinom halkasında çalışan bir elek kurar. Normal taşımalı çarpma yerine, katsayıların mod \(2\) toplandığı carryless çarpım kullanılır.
Şu eşleme
$$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$$
sayının ikili basamaklarını polinom katsayılarına dönüştürür. Bu modelde bit düzeyindeki XOR, \(\mathbb F_2[x]\) içindeki toplamanın aynısıdır. Eğer \(a\leftrightarrow A(x)\) ve \(b\leftrightarrow B(x)\) ise XOR-çarpım
$$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j)$$
şeklindedir. Dolayısıyla bir sayı ancak ve ancak polinomu \(\mathbb F_2\) üzerinde ayrışıyorsa XOR-bileşiktir.
\(n\) çiftse en düşük biti \(0\)'dır; bu da \(P_n(x)\) polinomunun sabit teriminin \(0\) olduğu anlamına gelir. O halde
$$P_n(x)=xQ(x)$$
yazılabilir. Bu yüzden \(2\)'den büyük her çift kod otomatik olarak XOR-bileşiktir. Tek çift XOR-prime değer
$$2\leftrightarrow x$$
olur; çünkü \(x\) birinci dereceden ve indirgenemezdir. Uygulamaların önce \(2\)'yi sayıp sonra yalnızca tek sayıları elemesinin nedeni budur.
\(p\) bir tek XOR-prime olsun ve ikili uzunluğu \(\ell\) olsun. Buna karşılık gelen polinomun derecesi
$$\deg P_p=\ell-1$$
olur. \(p\)'yi çarpan olarak içeren her tek XOR-bileşik sayı
$$P_n(x)=P_p(x)\,Q(x)$$
biçiminde yazılır; burada \(Q(x)\), sabit terimi \(1\) olan başka bir sabit olmayan polinomdur. Eğer \(Q\)'nun derecesi \(j\) ise
$$\deg P_n=(\ell-1)+j$$
olur. Arama aralığı \(2^M\)'nin altında kaldığı için
$$\deg P_n\le M-1$$
olmalı, yani
$$j\le M-\ell.$$
Elek bu koşulu sağlayan tüm çarpımları işaretler. Bütün bu işaretlemelerden sonra ayakta kalan tek kodlar indirgenemez olmak zorundadır.
Bir \(j\) ortak çarpan derecesi sabitlensin. Derecesi \(j\) olan her monik polinomun kodu
$$2^j\oplus t,\qquad 0\le t\lt 2^j$$
şeklindedir; çünkü en üst bit mutlaka \(1\)'dir ve alttaki \(j\) katsayı serbesttir. Bu nedenle sabit bir \(p\) için işaretlenmesi gereken değerler
$$p\otimes(2^j\oplus t)$$
biçimindedir. Burada \(\otimes\) carryless çarpımı gösterir. Bu derece için tam olarak \(2^j\) farklı ortak çarpan vardır ve uygulamalar bunların hepsini üretir.
Her carryless çarpımı sıfırdan hesaplamak pahalı olurdu. Bunun yerine uygulamalar alt kısmı \(t\) değerlerini Gray kod sırasıyla dolaşır. \(g_0=0\) olmak üzere
$$g_n=g_{n-1}\oplus \operatorname{lowbit}(n)$$
tanımını kullanalım; burada \(\operatorname{lowbit}(n)\), \(n\)'in en düşük anlamlı \(1\) bitidir. Bu sıra, \([0,2^j)\) aralığındaki her değeri tam bir kez gezer ve ardışık iki değer yalnızca tek bir bitte farklıdır. Eğer ortak çarpan tek bir \(2^r\) biti kadar değişirse, çarpım da yalnızca
$$p\otimes 2^r$$
kadar değişir. Bu ise \(2^r\) tek terimli \(x^r\)'yi temsil ettiği için sadece \(p\)'nin sola kaydırılmış halidir. Böylece sıradaki işaretlenecek değer, önceki değerden tek bir XOR ve tek bir kaydırılmış kopya ile elde edilir.
Elek yalnızca
$$j\ge \ell-1$$
olan ortak çarpan derecelerine ihtiyaç duyar. Bu, klasik Eratosthenes eleğinde \(p^2\)'den başlama fikrinin polinom karşılığıdır. Eğer \(P_n=P_pQ\) ve \(\deg Q\lt \deg P_p\) ise, \(Q\) polinomunun içinde \(P_p\)'den daha küçük dereceli bir indirgenemez çarpan bulunur. O zaman \(n\), o daha küçük dereceli çarpan işlendiğinde zaten işaretlenmiş olur. Yani eşit dereceden başlamak fazladan işi azaltır ama hiçbir bileşik değeri kaçırmaz.
İlk birkaç XOR-prime değerini polinom olarak yazarsak
$$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1$$
elde edilir. Yakındaki bazı tek sayılar XOR anlamında bileşiktir. Örneğin
$$5\leftrightarrow x^2+1=(x+1)^2,$$
$$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$$
Bu yüzden \(5\) ve \(9\) elenir, \(7\) ise kalır. Artan sıradaki sağ kalan değerler
$$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$$
şeklinde başlar. Dolayısıyla \(10\). XOR-prime değeri \(41\)'dir; uygulamaların küçük doğrulama noktası da budur.
C++, Python ve Java uygulamaları, \(2^M\)'den küçük tüm sayılar için bir işaret tablosu ayırır ve başlangıçta her girdiyi olası XOR-prime kabul eder. Önce \(2\) sayılır; ardından yalnızca tek kodlar artan sırayla taranır. Bir tek kod hâlâ işaretlenmemişse, bir sonraki XOR-prime bulunmuş olur ve sıra sayacı artırılır.
Her böyle aday için uygulama önce bit uzunluğunu alır; bu değer karşılık gelen polinomun derecesini verir. Sonra tüm uygun ortak çarpan dereceleri \(j\) üzerinde dolaşır. Her \(j\) için başlangıç noktası \(x^j\) ile çarpımdır; bu yalnızca sola kaydırma demektir. Ardından derece \(j\) olan bütün monik ortak çarpanlar Gray kod sırasıyla üretilir ve ortaya çıkan her çarpım XOR-bileşik olarak işaretlenir.
Temel hız kazancı şuradan gelir: ardışık iki ortak çarpan yalnızca tek bir alt bitte farklıdır. Bu yüzden yeni çarpım, eski çarpımdan taban polinomun kaydırılmış bir kopyasıyla tek XOR yapılarak elde edilir. İstenen sıra \(N\)'ye ulaşılır ulaşılmaz arama durur.
İşaret tablosunun boyutu \(2^M\) olduğundan bellek kullanımı \(O(2^M)\)'dir. Tek sayılar üzerindeki dış tarama da \(O(2^M)\) düzeyindedir. Derecesi \(d\) olan bir XOR-prime için işaretleme yükü
$$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d$$
olur. Bu nedenle kaba bir üst sınır \(O(M2^M)\) zamandır. Pratikte sabitler düşüktür; çünkü iç döngü birkaç bit işlemi dışında bir şey yapmaz ve işaretleme turları yalnızca gerçekten ayakta kalan XOR-prime değerler için çalışır.
Debemos encontrar el \(N\)-ésimo XOR-primo entre los enteros menores que \(2^M\). La reinterpretación clave es que el entero no se estudia con la aritmética usual, sino como un polinomio sobre \(\mathbb F_2\). Si
$$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$$
entonces representa
$$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x].$$
Así, un XOR-primo es un entero cuyo polinomio asociado es irreducible en \(\mathbb F_2[x]\). Las implementaciones los enumeran en orden creciente del valor entero. El caso par especial \(2\), que corresponde a \(x\), se cuenta primero; después de eso, todo XOR-primo restante es impar.
La solución construye una criba dentro del anillo polinómico \(\mathbb F_2[x]\). En lugar de la multiplicación ordinaria con acarreos, usa multiplicación sin acarreo, que coincide con multiplicar polinomios y reducir los coeficientes módulo \(2\).
La correspondencia
$$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$$
convierte los bits de \(n\) en coeficientes polinómicos. Bajo esta codificación, el XOR bit a bit es exactamente la suma en \(\mathbb F_2[x]\). Si \(a\leftrightarrow A(x)\) y \(b\leftrightarrow B(x)\), entonces el XOR-producto viene dado por
$$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j).$$
Por tanto, un número es XOR-compuesto si y solo si su polinomio factoriza de manera no trivial sobre \(\mathbb F_2\).
Si \(n\) es par, su bit menos significativo vale \(0\), luego el término constante de \(P_n(x)\) es \(0\). Eso implica
$$P_n(x)=xQ(x).$$
En consecuencia, todo código par mayor que \(2\) es automáticamente XOR-compuesto. El único XOR-primo par es
$$2\leftrightarrow x,$$
porque \(x\) tiene grado \(1\) y es irreducible. Por eso las implementaciones cuentan primero el \(2\) y después criban solo los enteros impares.
Sea \(p\) un XOR-primo impar, y sea \(\ell\) la longitud binaria de su código. Entonces
$$\deg P_p=\ell-1.$$
Cualquier XOR-compuesto impar que tenga a \(p\) como factor puede escribirse como
$$P_n(x)=P_p(x)\,Q(x),$$
donde \(Q(x)\) es otro polinomio no constante cuyo término constante es \(1\). Si \(Q\) tiene grado \(j\), entonces
$$\deg P_n=(\ell-1)+j.$$
Como la búsqueda se limita a los enteros menores que \(2^M\), se necesita
$$\deg P_n\le M-1,$$
de modo que
$$j\le M-\ell.$$
La criba marca todos esos productos. Todo código impar que sobreviva a todas las marcas debe ser irreducible.
Fijemos un grado \(j\). Todo polinomio mónico de grado \(j\) tiene código
$$2^j\oplus t,\qquad 0\le t\lt 2^j,$$
porque el bit superior debe ser \(1\) y los \(j\) coeficientes inferiores son libres. Por tanto, para una base \(p\), los valores a marcar son
$$p\otimes(2^j\oplus t),$$
donde \(\otimes\) denota la multiplicación sin acarreo. Para este grado hay exactamente \(2^j\) cofactores posibles, y las implementaciones los recorren todos.
Recalcular cada producto sin acarreo desde cero sería demasiado costoso. En su lugar, las implementaciones recorren los valores \(t\) en orden Gray. Partiendo de \(g_0=0\), se define
$$g_n=g_{n-1}\oplus \operatorname{lowbit}(n),$$
donde \(\operatorname{lowbit}(n)\) es el bit encendido menos significativo de \(n\). Así se visita cada valor de \([0,2^j)\) exactamente una vez, y dos valores consecutivos difieren en un solo bit. Si el cofactor cambia en un único bit \(2^r\), entonces el producto cambia solo en
$$p\otimes 2^r,$$
que no es más que una traslación a la izquierda de \(p\), porque \(2^r\) representa el monomio \(x^r\). De este modo, el siguiente valor marcado se obtiene del anterior con un solo XOR contra una copia desplazada del polinomio base.
La criba solo necesita cofactores con grado
$$j\ge \ell-1.$$
Esto es el análogo polinómico de comenzar la criba clásica en \(p^2\). Si \(P_n=P_pQ\) con \(\deg Q\lt \deg P_p\), entonces \(Q\) contiene algún factor irreducible de grado menor que el de \(P_p\), de modo que \(n\) ya habrá sido marcado cuando se procesó ese factor más pequeño. Empezar en el grado igual elimina trabajo redundante sin dejar pasar ningún compuesto.
Los primeros XOR-primos se escriben como
$$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1.$$
Algunos impares cercanos son compuestos en el sentido XOR por razones puramente polinómicas. Por ejemplo,
$$5\leftrightarrow x^2+1=(x+1)^2,$$
$$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$$
Así, \(5\) y \(9\) quedan marcados, mientras que \(7\) sobrevive. Los supervivientes en orden creciente comienzan como
$$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$$
Por consiguiente, el \(10\)-ésimo XOR-primo es \(41\), que coincide con el pequeño punto de control usado por las implementaciones.
Las implementaciones en C++, Python y Java reservan una tabla de marcas para todos los enteros menores que \(2^M\) y al principio consideran que cada entrada podría ser XOR-prima. Primero cuentan el \(2\), y luego recorren solo los códigos impares en orden ascendente. Cuando un código impar sigue sin marcarse, la implementación ha encontrado el siguiente XOR-primo y aumenta el contador de posición.
Para cada superviviente, la implementación calcula su longitud binaria, que determina el grado del polinomio asociado. Después recorre todos los grados de cofactor \(j\) permitidos. Para cada \(j\), empieza con el producto por \(x^j\), que es simplemente un desplazamiento a la izquierda, y luego recorre en orden Gray todos los cofactores mónicos de grado \(j\). Cada producto generado se marca como XOR-compuesto.
La optimización decisiva es que dos cofactores consecutivos solo difieren en un bit inferior. Por eso, el siguiente producto se obtiene del anterior con un único XOR contra una copia desplazada del polinomio base. La búsqueda termina en cuanto se alcanza el rango pedido \(N\).
La tabla de marcas tiene tamaño \(2^M\), así que la memoria es \(O(2^M)\). El barrido exterior sobre los enteros impares también cuesta \(O(2^M)\). Para un XOR-primo superviviente de grado \(d\), el trabajo de marcado es
$$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d.$$
Una cota global simple es, por tanto, \(O(M2^M)\) tiempo. En la práctica las constantes son pequeñas, porque el bucle interior solo realiza operaciones bit a bit y las fases de marcado solo se lanzan para XOR-primos que realmente sobreviven.
题目要求在所有小于 \(2^M\) 的整数中找出第 \(N\) 个 XOR-素数。这里的“素数”不是通常整数乘法意义下的素数，而是把整数看成 \(\mathbb F_2\) 上的多项式之后的不可约元。若
$$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$$
则它对应的多项式是
$$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x].$$
因此，一个整数是 XOR-素数，当且仅当对应多项式在 \(\mathbb F_2[x]\) 中不可约。实现按照整数值从小到大的顺序计数。特殊的偶数 \(2\) 对应多项式 \(x\)，它要先单独计入；在它之后，其余 XOR-素数全部都是奇数。
整个解法本质上是在多项式环 \(\mathbb F_2[x]\) 中做筛法。它不用普通带进位的整数乘法，而是使用无进位乘法，也就是系数按模 \(2\) 相加的多项式乘法。
映射
$$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$$
把整数的二进制位直接变成多项式系数。在这个模型里，按位 XOR 恰好就是 \(\mathbb F_2[x]\) 里的加法。若 \(a\leftrightarrow A(x)\)、\(b\leftrightarrow B(x)\)，那么对应的 XOR 乘法为
$$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j).$$
这说明所谓 XOR-合数，等价于对应多项式在 \(\mathbb F_2\) 上可以做非平凡分解。
如果 \(n\) 是偶数，那么它最低位是 \(0\)，因此 \(P_n(x)\) 的常数项也是 \(0\)。这意味着
$$P_n(x)=xQ(x).$$
于是所有大于 \(2\) 的偶数编码都会被 \(x\) 整除，必然是 XOR-合数。唯一的偶数 XOR-素数就是
$$2\leftrightarrow x,$$
因为 \(x\) 是一次多项式，自然不可约。也正因为如此，实现一开始就把 \(2\) 计入，然后只筛奇数。
设 \(p\) 是一个奇数 XOR-素数，其二进制长度为 \(\ell\)。那么对应多项式的次数为
$$\deg P_p=\ell-1.$$
任何一个以 \(p\) 为因子的奇数 XOR-合数，都可以写成
$$P_n(x)=P_p(x)\,Q(x),$$
其中 \(Q(x)\) 是另一个非常数多项式，而且常数项为 \(1\)。若 \(Q\) 的次数是 \(j\)，则
$$\deg P_n=(\ell-1)+j.$$
由于只考虑小于 \(2^M\) 的数，所以必须满足
$$\deg P_n\le M-1,$$
也就是
$$j\le M-\ell.$$
筛法所做的事，就是把所有满足这个条件的乘积全部标记为 XOR-合数。一个奇数编码如果在所有标记之后依然存活，就只能对应不可约多项式。
固定余因子次数 \(j\)。所有次数恰好为 \(j\) 的首一多项式，其编码都可以写成
$$2^j\oplus t,\qquad 0\le t\lt 2^j,$$
因为最高位必须为 \(1\)，其余低 \(j\) 位可以任意取值。于是，对固定的基多项式 \(p\)，需要标记的值正是
$$p\otimes(2^j\oplus t),$$
其中 \(\otimes\) 表示无进位乘法。对于这个固定次数，一共有 \(2^j\) 个不同的首一余因子，实现会把它们全部遍历出来。
如果每次都从头重算无进位乘法，代价会很高。实现采用的办法是：把低位部分 \(t\) 按 Gray 码顺序遍历。令 \(g_0=0\)，并定义
$$g_n=g_{n-1}\oplus \operatorname{lowbit}(n),$$
其中 \(\operatorname{lowbit}(n)\) 表示 \(n\) 的最低非零位。这样得到的序列会把 \([0,2^j)\) 中的每一个值恰好访问一次，而且相邻两个值只在一位上不同。若余因子只改变了一位 \(2^r\)，那么乘积只会改变
$$p\otimes 2^r.$$
而 \(2^r\) 对应单项式 \(x^r\)，所以这一步不过是把 \(p\) 左移若干位。于是，下一个要标记的乘积可以由上一个乘积经过一次 XOR 和一次移位得到，不必重新做完整乘法。
筛法只需要处理满足
$$j\ge \ell-1$$
的余因子次数。这正是普通埃拉托斯特尼筛法从 \(p^2\) 开始标记的多项式版本。若有分解 \(P_n=P_pQ\) 且 \(\deg Q\lt \deg P_p\)，那么 \(Q\) 内部必然含有某个次数更小的不可约因子。这样一来，\(n\) 在处理那个更小次数因子时就已经会被标记掉。因此从相同次数开始即可，既不会漏掉任何合数，又避免了明显重复的工作。
前几个 XOR-素数写成多项式是
$$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1.$$
一些看起来很近的奇数，其实在 XOR 意义下是合数。例如
$$5\leftrightarrow x^2+1=(x+1)^2,$$
$$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$$
因此 \(5\) 和 \(9\) 会被筛掉，而 \(7\) 会保留下来。按整数值递增列出存活者，开头是
$$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$$
所以第 \(10\) 个 XOR-素数是 \(41\)。这也正是实现所匹配的小型校验点。
C++、Python 和 Java 实现都会先分配一个长度为 \(2^M\) 的标记表，初始时把所有位置都看成“可能是 XOR-素数”。随后先把 \(2\) 计入答案，再只扫描奇数编码。每当一个奇数位置还没有被标记时，实现就知道它找到了下一个 XOR-素数，并把当前排名加一。
对于每个这样的幸存者，实现先取它的二进制长度，从而得到对应多项式的次数。接着枚举所有允许的余因子次数 \(j\)。每个 \(j\) 都从与 \(x^j\) 的乘积开始，这一步只是左移；然后按 Gray 码顺序遍历所有次数为 \(j\) 的首一余因子，把生成的每个乘积都标记为 XOR-合数。
核心优化在于：相邻两个余因子只差一个低位，因此新乘积可以由旧乘积通过“与一份左移后的基多项式做一次 XOR”直接得到。这样内层循环只包含非常便宜的位运算。一旦排名达到所需的 \(N\)，搜索立即结束，不再做多余工作。
标记表大小是 \(2^M\)，所以空间复杂度为 \(O(2^M)\)。外层对奇数的扫描同样是 \(O(2^M)\)。对于一个次数为 \(d\) 的幸存 XOR-素数，其标记工作量为
$$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d.$$
因此一个简洁的最坏情况上界可以写成 \(O(M2^M)\) 时间。实际运行通常比这个粗上界更好，因为真正进入标记阶段的只有幸存的 XOR-素数，而且内层步骤几乎全是常数代价的位操作。
Нужно найти \(N\)-е XOR-простое число среди целых чисел, меньших \(2^M\). Здесь под «простотой» понимается не обычная арифметическая простота, а неприводимость соответствующего полинома над \(\mathbb F_2\). Если
$$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$$
то этому числу сопоставляется полином
$$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x].$$
Следовательно, XOR-простым является ровно тот код, чей полином неприводим в \(\mathbb F_2[x]\). Реализации перебирают такие числа в порядке возрастания обычного целого значения. Особый чётный случай \(2\), соответствующий полиному \(x\), учитывается отдельно и первым; после него все остальные XOR-простые уже нечётны.
Решение строит решето в кольце полиномов \(\mathbb F_2[x]\). Вместо обычного умножения с переносами используется умножение без переносов, то есть полиномиальное умножение с коэффициентами по модулю \(2\).
Соответствие
$$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$$
делает двоичные цифры числа коэффициентами полинома. При такой интерпретации побитовое XOR совпадает со сложением в \(\mathbb F_2[x]\). Если \(a\leftrightarrow A(x)\) и \(b\leftrightarrow B(x)\), то XOR-произведение записывается как
$$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j).$$
Значит, число XOR-составно тогда и только тогда, когда соответствующий полином нетривиально раскладывается над \(\mathbb F_2\).
Если \(n\) чётно, то его младший бит равен \(0\), а значит свободный член полинома \(P_n(x)\) тоже равен \(0\). Следовательно,
$$P_n(x)=xQ(x).$$
Поэтому любой чётный код больше \(2\) автоматически является XOR-составным. Единственное чётное XOR-простое число — это
$$2\leftrightarrow x,$$
поскольку \(x\) имеет степень \(1\) и неприводим. Именно поэтому реализации сразу учитывают \(2\), а затем просеивают только нечётные числа.
Пусть \(p\) — нечётное XOR-простое число, а \(\ell\) — длина его двоичной записи. Тогда степень соответствующего полинома равна
$$\deg P_p=\ell-1.$$
Любое нечётное XOR-составное число, имеющее \(p\) в качестве множителя, представимо в виде
$$P_n(x)=P_p(x)\,Q(x),$$
где \(Q(x)\) — другой неконстантный полином со свободным членом \(1\). Если степень \(Q\) равна \(j\), то
$$\deg P_n=(\ell-1)+j.$$
Так как рассматриваются только числа меньше \(2^M\), необходимо условие
$$\deg P_n\le M-1,$$
то есть
$$j\le M-\ell.$$
Решето помечает все такие произведения. Следовательно, любой нечётный код, который пережил все пометки, обязан соответствовать неприводимому полиному.
Зафиксируем степень кофактора \(j\). Любой монический полином степени \(j\) имеет код
$$2^j\oplus t,\qquad 0\le t\lt 2^j,$$
потому что старший бит обязан быть равен \(1\), а нижние \(j\) коэффициентов выбираются свободно. Значит, для данного базового полинома \(p\) нужно пометить значения
$$p\otimes(2^j\oplus t),$$
где \(\otimes\) обозначает умножение без переносов. Для каждой такой степени существует ровно \(2^j\) допустимых кофакторов, и реализации перечисляют их полностью.
Пересчитывать каждое произведение без переносов с нуля было бы слишком дорого. Поэтому реализации обходят значения \(t\) в порядке кода Грея. Пусть \(g_0=0\), а далее
$$g_n=g_{n-1}\oplus \operatorname{lowbit}(n),$$
где \(\operatorname{lowbit}(n)\) — младший установленный бит числа \(n\). Такая последовательность проходит все значения из \([0,2^j)\) ровно по одному разу, причём соседние значения отличаются только в одном бите. Если кофактор меняется на один бит \(2^r\), то произведение меняется лишь на
$$p\otimes 2^r,$$
а это просто сдвиг \(p\) влево, поскольку \(2^r\) соответствует моному \(x^r\). Значит, следующее помечаемое значение получается из предыдущего одной операцией XOR со сдвинутой копией базового кода.
Решету достаточно рассматривать только кофакторы со степенью
$$j\ge \ell-1.$$
Это полиномиальный аналог того, что в классическом решете Эратосфена начинают с \(p^2\). Если \(P_n=P_pQ\) и \(\deg Q\lt \deg P_p\), то внутри \(Q\) обязательно есть некоторый неприводимый множитель меньшей степени, чем у \(P_p\). Тогда число \(n\) уже будет помечено при обработке этого меньшего множителя. Старт с равной степени убирает лишнюю работу и при этом не пропускает ни одного составного случая.
Первые XOR-простые удобно выписать в полиномиальной форме:
$$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1.$$
Некоторые близкие нечётные числа оказываются XOR-составными по чисто полиномиальным причинам. Например,
$$5\leftrightarrow x^2+1=(x+1)^2,$$
$$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$$
Поэтому \(5\) и \(9\) будут помечены, а \(7\) останется. Последовательность выживших кодов в порядке возрастания начинается так:
$$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$$
Следовательно, \(10\)-е XOR-простое равно \(41\), и именно этот небольшой контрольный результат совпадает у реализаций.
Реализации на C++, Python и Java выделяют таблицу пометок для всех чисел меньше \(2^M\) и сначала считают, что каждая позиция потенциально XOR-простая. Сначала отдельно засчитывается число \(2\), затем в порядке возрастания просматриваются только нечётные коды. Если очередной нечётный код ещё не помечен, значит найдено следующее XOR-простое и текущий ранг увеличивается на единицу.
Для каждого такого выжившего значения реализация вычисляет длину двоичной записи, а значит и степень соответствующего полинома. Затем перебираются все допустимые степени кофактора \(j\). Для каждого \(j\) стартовая точка — это произведение на \(x^j\), то есть обычный сдвиг влево. После этого все монические кофакторы степени \(j\) обходятся в порядке кода Грея, и каждое полученное произведение помечается как XOR-составное.
Главная оптимизация состоит в том, что соседние кофакторы отличаются ровно одним младшим битом. Поэтому новое произведение выводится из предыдущего одной операцией XOR со сдвинутой копией базового полинома. Как только счётчик достигает нужного значения \(N\), поиск немедленно завершается.
Таблица пометок имеет размер \(2^M\), значит память равна \(O(2^M)\). Внешний просмотр нечётных чисел тоже имеет порядок \(O(2^M)\). Для выжившего XOR-простого степени \(d\) объём работы по пометке равен
$$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d.$$
Поэтому простая грубая верхняя оценка по времени — \(O(M2^M)\). На практике константы малы: внутренний цикл состоит почти только из побитовых операций, а этапы пометки запускаются лишь для тех XOR-простых, которые действительно пережили предыдущие отметки.
المطلوب هو إيجاد العدد الأولي XOR رقم \(N\) بين جميع الأعداد الصحيحة الأصغر من \(2^M\). المقصود هنا ليس الأولية بالنسبة إلى الضرب المعتاد، بل عدم قابلية كثير الحدود الموافق للعدد للاختزال فوق \(\mathbb F_2\). فإذا كان
$$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$$
فإنه يقابل كثير الحدود
$$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x].$$
وعليه يكون العدد XOR-prime إذا وفقط إذا كان كثير الحدود الموافق له غير قابل للاختزال في \(\mathbb F_2[x]\). تقوم التطبيقات بترتيب هذه الأعداد حسب قيمتها الصحيحة التصاعدية. والحالة الزوجية الخاصة هي \(2\)، الموافق لكثير الحدود \(x\)، ولذلك تُحسب أولًا؛ وبعدها تصبح جميع قيم XOR-prime الأخرى فردية.
الحل يبني غربالًا داخل حلقة كثيرات الحدود \(\mathbb F_2[x]\). وبدل الضرب المعتاد الذي يتضمن حملًا، يستخدم ضربًا بلا حمل، وهو نفسه ضرب كثيرات الحدود مع أخذ المعاملات بترديد \(2\).
التحويل
$$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$$
يجعل البتات الثنائية للعدد معاملاتٍ لكثير الحدود. وضمن هذا التمثيل يصبح XOR على مستوى البتات هو نفسه الجمع في \(\mathbb F_2[x]\). فإذا كان \(a\leftrightarrow A(x)\) و\(b\leftrightarrow B(x)\)، فإن حاصل الضرب من نوع XOR يكتب بالشكل
$$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j).$$
ومن ثم يكون العدد XOR-مركبًا بالضبط عندما يتفكك كثير الحدود الموافق له تفكيكًا غير تافه فوق \(\mathbb F_2\).
إذا كان \(n\) زوجيًا فإن أقل بت فيه يساوي \(0\)، وهذا يعني أن الحد الثابت في \(P_n(x)\) يساوي \(0\). لذلك يمكن كتابة
$$P_n(x)=xQ(x).$$
إذن كل ترميز زوجي أكبر من \(2\) يكون XOR-مركبًا تلقائيًا. والعدد الزوجي الوحيد الذي يبقى XOR-prime هو
$$2\leftrightarrow x,$$
لأن \(x\) كثير حدود من الدرجة الأولى، وبالتالي هو غير قابل للاختزال. ولهذا السبب تبدأ التطبيقات بعدّ \(2\) مباشرة ثم تكتفي بغربلة الأعداد الفردية.
لنفرض أن \(p\) عدد XOR-prime فردي، وأن طول تمثيله الثنائي هو \(\ell\). عندئذ تكون درجة كثير الحدود الموافق له
$$\deg P_p=\ell-1.$$
وكل عدد XOR-مركب فردي يملك \(p\) عاملًا يمكن كتابته على الصورة
$$P_n(x)=P_p(x)\,Q(x),$$
حيث \(Q(x)\) كثير حدود آخر غير ثابت وحده الثابت يساوي \(1\). إذا كانت درجة \(Q\) تساوي \(j\)، فإن
$$\deg P_n=(\ell-1)+j.$$
وبما أن البحث محصور في الأعداد الأصغر من \(2^M\)، فلا بد من تحقق
$$\deg P_n\le M-1,$$
أي
$$j\le M-\ell.$$
يقوم الغربال بتعليم جميع هذه النواتج. وأي ترميز فردي ينجو من جميع عمليات التعليم لا بد أن يكون موافقًا لكثير حدود غير قابل للاختزال.
ثبّت درجة العامل المرافق \(j\). كل كثير حدود أحادي من الدرجة \(j\) يملك الترميز
$$2^j\oplus t,\qquad 0\le t\lt 2^j,$$
لأن أعلى بت يجب أن يكون \(1\)، بينما تبقى المعاملات الأدنى وعددها \(j\) حرة. لذلك فإن القيم التي يجب تعليمها لعامل أساس ثابت \(p\) هي
$$p\otimes(2^j\oplus t),$$
حيث ترمز \(\otimes\) إلى الضرب بلا حمل. ولكل درجة ثابتة يوجد بالضبط \(2^j\) عاملًا مرافقًا ممكنًا، وتقوم التطبيقات بتعدادها جميعًا.
إعادة حساب كل ضرب بلا حمل من البداية ستكون مكلفة جدًا. لذلك تمرّ التطبيقات على القيم \(t\) بترتيب Gray. إذا وضعنا \(g_0=0\) ثم عرّفنا
$$g_n=g_{n-1}\oplus \operatorname{lowbit}(n),$$
حيث تمثل \(\operatorname{lowbit}(n)\) أقل بت مفعّل في \(n\)، فإن هذه السلسلة تزور كل قيمة في المجال \([0,2^j)\) مرة واحدة تمامًا، كما أن قيمتين متتاليتين تختلفان في بت واحد فقط. وإذا تغيّر العامل المرافق بمقدار البت الوحيد \(2^r\)، فإن الناتج يتغير فقط بمقدار
$$p\otimes 2^r.$$
وهذا ليس إلا إزاحة لليسار للعدد \(p\)، لأن \(2^r\) يمثّل الحد الأحادي \(x^r\). وبهذا تُستخرج القيمة التالية المراد تعليمها من السابقة بعملية XOR واحدة مع نسخة مزاحة من العامل الأساس.
لا يحتاج الغربال إلا إلى العوامل المرافقة التي تحقق
$$j\ge \ell-1.$$
وهذا هو النظير متعدد الحدود لفكرة البدء من \(p^2\) في غربال إراتوستينس التقليدي. فإذا كان لدينا \(P_n=P_pQ\) مع \(\deg Q\lt \deg P_p\)، فإن \(Q\) يحتوي عاملًا غير قابل للاختزال درجته أصغر من درجة \(P_p\). وعند معالجة ذلك العامل الأصغر سيكون \(n\) قد عُلِّم بالفعل. لذا فإن البدء من الدرجة المساوية يزيل العمل الزائد من غير أن يفوّت أي حالة مركبة.
أوائل أعداد XOR-prime تبدو على صورة كثيرات حدود كما يلي:
$$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1.$$
بعض الأعداد الفردية القريبة تكون XOR-مركبة لأسباب متعددة حدودية بحتة. فمثلًا
$$5\leftrightarrow x^2+1=(x+1)^2,$$
$$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$$
لذلك يُعلَّم كل من \(5\) و\(9\)، بينما يبقى \(7\) دون تعليم. وإذا سردنا القيم الباقية بترتيب تصاعدي نحصل في البداية على
$$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$$
ومن ثم يكون العدد XOR-prime العاشر هو \(41\)، وهو نفس التحقق الصغير الذي تطابقه التطبيقات.
تخصّص تطبيقات C++ وPython وJava جدول تعليم لجميع الأعداد الأصغر من \(2^M\)، وتفترض مبدئيًا أن كل موضع قد يكون XOR-prime. بعد احتساب \(2\) أولًا، يجري المسح على الترميزات الفردية فقط بترتيب تصاعدي. وكلما وُجد ترميز فردي غير معلَّم، فهذا يعني الوصول إلى XOR-prime جديد وزيادة الرتبة الحالية بمقدار واحد.
بعد ذلك تحسب الشيفرة طول التمثيل الثنائي لذلك الترميز، ومنه تُستنتج درجة كثير الحدود الموافق. ثم تدور على جميع درجات العوامل المرافقة المسموح بها \(j\). ولكل \(j\) تبدأ من الضرب في \(x^j\)، أي من إزاحة يسارية مباشرة، ثم تمر على جميع العوامل الأحادية من الدرجة \(j\) بترتيب Gray. وكل حاصل ضرب يتم توليده يُعلَّم على أنه XOR-مركب.
جوهر التحسين أن عاملين مرافقين متتاليين لا يختلفان إلا في بت منخفض واحد، ولذلك يمكن اشتقاق الناتج الجديد من الناتج السابق بواسطة XOR واحد مع نسخة مزاحة من كثير الحدود الأساس. وتتوقف عملية البحث مباشرة عند الوصول إلى الرتبة المطلوبة \(N\).
حجم جدول التعليم هو \(2^M\)، لذلك فالتعقيد المكاني يساوي \(O(2^M)\). كما أن المسح الخارجي على الأعداد الفردية يقع في \(O(2^M)\). وبالنسبة إلى XOR-prime ناجٍ درجته \(d\)، فإن كلفة التعليم تساوي
$$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d.$$
ومن ثم يمكن تلخيص حد أعلى بسيط للزمن على أنه \(O(M2^M)\). عمليًا تكون الثوابت صغيرة، لأن الحلقة الداخلية لا تقوم إلا بعمليات بتية، ولأن مراحل التعليم لا تُطلق إلا للعوامل التي ظلت باقية بعد المراحل السابقة.