🔢 mathematics

Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

Diese Arbeit präsentiert eine Klassifizierung von Carmichael-Zahlen und einen effizienten Algorithmus zur Generierung neuer Euler-Pseudoprimzahlen, wodurch eine Zahl entdeckt wurde, die als Pseudoprimzahl für die ersten 47 Primzahlenbasen (bis 211) besteht.

Ursprüngliche Autoren: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

Veröffentlicht 2026-02-26

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Alejandra Alcantarilla Sánchez, Jolijn Cottaar, Tanja Lange, Benne de Weger

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stell dir vor, du bist ein Türsteher in einem sehr exklusiven Club. Der Club heißt „Primzahlen". Nur echte Primzahlen dürfen rein. Aber das Problem ist: Es gibt viele Betrugsversuche. Es gibt Zahlen, die sich wie Primzahlen verhalten, aber im Inneren eigentlich zusammengesetzt sind. Diese nennt man Pseudoprimzahlen.

Um die echten von den falschen zu unterscheiden, haben die Türsteher einen Test: Sie fragen die Zahl eine Frage. Wenn die Zahl die Antwort richtig gibt, darf sie rein. Wenn sie falsch liegt, wird sie rausgeworfen.

Das Problem: Manche Betrüger sind so schlau, dass sie die Antwort auf fast jede Frage richtig geben. Sie sind die „Super-Betrüger".

In diesem Papier haben sich vier Forscher (Alejandra, Jolijn, Tanja und Benne) vorgenommen, den ultimativen Super-Betrüger zu finden. Ihr Ziel war es, eine Zahl zu konstruieren, die den Test für 47 verschiedene Fragen (basierend auf den ersten 47 Primzahlen) besteht. Das ist ein Rekord! Die Zahl, die sie gefunden haben, ist so groß, dass sie 1230 Bits lang ist – das ist wie ein riesiger Datenschatz.

Hier ist die Geschichte, wie sie das gemacht haben, einfach erklärt:

1. Die Suche nach den perfekten Betrügern (Karmichael-Zahlen)

Normalerweise suchen die Forscher nach zufälligen Zahlen und testen sie. Aber sie merkten schnell: Die besten Betrüger sind keine zufälligen Zahlen. Sie sind eine spezielle Sorte, die Karmichael-Zahlen genannt werden.

Stell dir diese Karmichael-Zahlen wie Meister-Schmiede vor. Sie können sich in jede Form verwandeln, die der Türsteher (der Test) erwartet. Wenn der Türsteher sagt: „Zeig mir, dass du eine Primzahl bist!", machen die Karmichael-Zahlen genau das, was eine Primzahl tun würde.

Die Forscher teilten diese Meister-Schmiede in zwei Gruppen ein:

Gruppe A: Diese sind die Besten. Sie haben eine Eigenschaft, die es ihnen erlaubt, fast immer die richtige Antwort zu geben.
Gruppe B: Diese sind etwas weniger zuverlässig.

Die Forscher entschieden sich, nur mit Gruppe A zu arbeiten, weil diese die höchsten Chancen haben, den Test zu bestehen.

2. Das Legospiel: Zahlen multiplizieren

Jetzt kam der geniale Trick. Die Forscher dachten sich: „Was wäre, wenn wir zwei dieser Super-Betrüger zusammenkleben?"

Stell dir vor, du hast zwei sehr gute Lügner. Wenn du sie zu einem Team zusammenschließt, wird das Team noch besser?

Wenn Lügner A sagt: „Ich bin eine Primzahl!" und Lügner B sagt: „Ich bin auch eine Primzahl!", dann sagt das Team: „Wir sind eine Primzahl!"
Das Besondere ist: Weil die beiden Lügner so gut sind, dass sie den Test für die ersten 10 Fragen bestehen, schafft es ihr Team oft, den Test für die ersten 11 oder 12 Fragen zu bestehen.

Die Forscher haben also wie bei Lego angefangen:

Sie nahmen kleine, gute Bausteine (kleine Karmichael-Zahlen).
Sie haben sie paarweise zu größeren Blöcken zusammengefügt.
Dann haben sie diese größeren Blöcke wieder zu noch größeren Blöcken zusammengefügt.

Jedes Mal, wenn sie zwei Blöcke zusammenklebten, entstand eine neue, riesige Zahl, die noch mehr Fragen richtig beantworten konnte als ihre Eltern.

3. Der Filter: Nur die Besten rein

Beim Zusammenkleben passierten aber auch Fehler. Manchmal entstand eine Zahl, die nicht mehr „sauber" war (sie hatte doppelte Faktoren, wie ein Lego-Block, der doppelt so dick ist, wie er sollte). Solche Zahlen wurden sofort aussortiert.

Außerdem filterten sie Zahlen raus, die zu kleine Bausteine hatten (Zahlen mit kleinen Primfaktoren), weil diese leicht zu durchschauen waren. Sie wollten nur die schwersten, komplexesten Betrüger.

4. Das Ergebnis: Der Champion

Nachdem sie diesen Prozess immer und immer wieder wiederholten (wie ein Computer, der Millionen von Lego-Kombinationen durchprobiert), fanden sie den ultimativen Champion.

Diese Zahl ist so schlau, dass sie den Türsteher-Test für die ersten 47 Fragen besteht.

Die Fragen basieren auf den ersten 47 Primzahlen (2, 3, 5, 7, ..., 211).
Die Zahl ist so groß, dass sie 1230 Bits lang ist. Zum Vergleich: Ein normaler Text von ein paar Sätzen ist viel kürzer. Diese Zahl ist wie ein ganzer Roman, der nur aus Zahlen besteht.

Warum ist das wichtig?

In der Welt der Kryptografie (Verschlüsselung) brauchen wir Primzahlen, um sichere Schlüssel zu machen (wie bei deinem Online-Banking). Wenn jemand absichtlich eine dieser „Super-Betrüger"-Zahlen in dein System einschleust, könnte er deine Verschlüsselung knacken.

Indem die Forscher diese extremen Betrüger finden, zeigen sie:

Wie gefährlich sie sein können.
Wie man bessere Tests entwickelt, um sie zu erkennen.

Zusammenfassung in einem Satz:
Die Forscher haben wie Architekten aus kleinen, perfekten Lügen-Steinen (Karmichael-Zahlen) einen riesigen, undurchdringlichen Lügen-Turm gebaut, der so schlau ist, dass er 47 verschiedene Sicherheitschecks hintereinander besteht, bevor er als Betrüger entlarvt wird.

1. Problemstellung und Motivation

Öffentliche Schlüsselkryptosysteme wie RSA und Diffie-Hellman benötigen große Primzahlen für ihre Sicherheit. Da der deterministische Primzahltest für sehr große Zahlen rechenintensiv ist, verlassen sich Implementierungen auf probabilistische Tests wie den Miller-Rabin-Test oder den Solovay-Strassen-Test.

Der Solovay-Strassen-Test prüft für eine Kandidatenzahl $n$ und eine Basis $a$ , ob die Euler-Kriterium-Gleichung $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$ gilt.
Eine zusammengesetzte Zahl, die diesen Test für eine bestimmte Basis besteht, wird Euler-Pseudoprimzahl genannt. Die Basis $a$ wird in diesem Fall als „Euler-Lügner" (Euler liar) bezeichnet.
Das Problem: Wenn ein Angreifer in der Lage ist, zusammengesetzte Zahlen zu konstruieren, die für viele aufeinanderfolgende Primzahlen als Basen den Test bestehen, kann er die Primzahlgenerierung manipulieren und schwache Schlüssel erzeugen. Bisherige Arbeiten (z. B. von Sorenson und Webster) zeigten starke Pseudoprimzahlen für die ersten 12 Primzahlen. Das Ziel dieses Papers ist es, Euler-Pseudoprimzahlen zu finden, die für eine noch größere Anzahl von Basen bestehen.

2. Methodik und theoretische Grundlagen

Klassifizierung von Carmichael-Zahlen

Da jede Euler-Pseudoprimzahl auch eine Fermat-Pseudoprimzahl ist, konzentrieren sich die Autoren auf Carmichael-Zahlen (zusammengesetzte Zahlen, die für alle zu $n$ teilerfremden Basen den Fermat-Test bestehen).
Die Autoren führen eine Klassifizierung von Carmichael-Zahlen basierend auf dem Index $i(n) = \frac{n-1}{\lambda(n)}$ ein, wobei $\lambda(n)$ die Carmichael-Funktion ist (das kleinste $k$ , sodass $a^k \equiv 1 \pmod n$ für alle $a \in \mathbb{Z}_n^*$ ).

Klasse A: $i(n)$ ist gerade. Hier gibt es genau $\frac{1}{2}\phi(n)$ Euler-Lügner, und alle haben den Jacobi-Symbol-Wert $+1$ . Dies ist die maximale Anzahl möglicher Lügner für eine zusammengesetzte Zahl.
Klasse B: $i(n)$ $i (n)$ ist ungerade. Diese wird weiter unterteilt in:
- B1: Eine Teilmenge der Primfaktoren hat eine bestimmte 2-adische Bewertung. Anzahl der Lügner: $\frac{1}{2^{h+1}}\phi(n)$ .
- B2: Alle Primfaktoren haben dieselbe 2-adische Bewertung. Anzahl der Lügner: $\frac{1}{2^{k-1}}\phi(n)$ , wobei Jacobi-Symbole $+1$ und $-1$ gleich oft vorkommen.

Erkenntnis: Klasse A bietet die höchste Wahrscheinlichkeit, viele Basen zu bestehen. Daher fokussiert sich die Suche auf Zahlen dieser Klasse.

Multiplikation von Pseudoprimzahlen

Ein zentraler algorithmischer Ansatz ist die Multiplikation bereits gefundener Euler-Pseudoprimzahlen, um größere zu erzeugen.

Lemma 13: Wenn zwei Carmichael-Zahlen $n_1, n_2$ aus Klasse A multipliziert werden und ihr Produkt $n = n_1 n_2$ ebenfalls eine Carmichael-Zahl in Klasse A ist, dann besteht das Produkt den Test für alle Basen, für die $n_1$ und $n_2$ bestanden haben, und zusätzlich für die nächste Primzahlbasis.
Dies liegt daran, dass für Klasse A der Exponent $a^{(n-1)/2} \equiv 1 \pmod n$ immer gilt. Die Bedingung reduziert sich auf das Jacobi-Symbol. Wenn $n_1$ und $n_2$ für eine Basis $b$ beide den Jacobi-Symbol-Wert $-1$ haben (da sie den Test bei $b$ gerade noch bestanden haben, aber bei der nächsten Basis versagen würden), dann ist das Produkt der Symbole $(-1) \cdot (-1) = 1$ , wodurch $b$ zum Lügner für das Produkt wird.

Filterung und Optimierung

Um die Suche effizient zu gestalten, wenden die Autoren mehrere Filter an:

Atomare Carmichael-Zahlen: Nur Zahlen, die nicht selbst Produkte anderer Carmichael-Zahlen sind, werden als Bausteine verwendet.
Kleine Faktoren: Zahlen mit kleinen Primfaktoren werden ausgeschlossen, da sie sofort für diese Basen versagen.
Klasse A-Fokus: Es wird nur multipliziert, wenn beide Faktoren in Klasse A sind und das Ergebnis wahrscheinlich auch in Klasse A liegt (basierend auf Bedingungen für $v_2(n-1)$ und $v_2(\lambda(n))$ ).
Modulo 120 Filter: Die Analyse zeigt, dass fast alle erfolgreichen Pseudoprimzahlen $\equiv 1 \pmod{120}$ sind.

3. Algorithmus

Die Autoren entwickeln einen Algorithmus (Algorithm 1), der wie folgt arbeitet:

Eingabe: Zwei Euler-Pseudoprimzahlen $n_1, n_2$ aus der gleichen Klasse $epsp(a)$ (bestehen Test bis Basis $a$ ).
Prüfung der Bedingungen für Klasse A (Vergleich der 2-adischen Bewertungen von $n-1$ und $\lambda(n)$ ).
Berechnung von $n = n_1 \cdot n_2$ und $\lambda(n) = \text{lcm}(\lambda(n_1), \lambda(n_2))$ .
Überprüfung, ob $n$ eine Carmichael-Zahl ist ( $\lambda(n) | (n-1)$ ).
Wenn ja, wird der Test für die nächste Primzahlbasis $b$ durchgeführt. Da $n$ in Klasse A ist, muss nur das Jacobi-Symbol $\left(\frac{b}{n}\right)$ geprüft werden.
Iteratives Fortschreiten durch die Primzahlen, solange das Jacobi-Symbol $+1$ bleibt.

4. Ergebnisse

Die Autoren haben eine große Anzahl neuer Euler-Pseudoprimzahlen generiert, indem sie die oben beschriebene Multiplikationsstrategie rekursiv anwendeten (z. B. $epsp_4[2]^2$ , $epsp_8$ , $epsp_{16}$ ).

Bestes Ergebnis: Sie fanden eine Euler-Pseudoprimzahl mit 1230 Bits, die den Solovay-Strassen-Test für die ersten 47 Primzahlen (bis zur Basis 211) besteht.
- Die Zahl ist: $29718025324240318410534115039052540117775597945085067414357453436601387742670453459355591542069934388905907314583289167399384127469613680383642792167067979229668463351656529527558991522533896182769739577451082067252281857005565209955278879251421652977184230025871827972345589832963084011984500975075999311171856228688510024383030748708219201214793184433340476692190457601$.
Statistik: Die Autoren zeigten, dass die Anzahl der gefundenen Pseudoprimzahlen exponentiell mit der Anzahl der Multiplikationsschritte abnimmt, aber durch die gezielte Auswahl von Klasse A-Zahlen und die Filterung nach kleinen Faktoren eine signifikante Anzahl von Kandidaten erhalten bleibt.
Sophie-Germinus-Pseudoprimzahlen: Als Nebenprodukt identifizierten die Autoren eine weitere Klasse von zusammengesetzten Zahlen ( $n = p_1(2p_1-1)$ ), die als „Sophie-Germinus-Pseudoprimzahlen" bezeichnet werden. Diese haben $\phi(n)/4$ Euler-Lügner und stellen eine Alternative zu Carmichael-Zahlen dar, sind aber für die Konstruktion extrem großer Pseudoprimzahlen weniger effizient als die Multiplikation von Carmichael-Zahlen.

5. Bedeutung und Fazit

Rekord: Das Paper stellt einen neuen Rekord für Euler-Pseudoprimzahlen auf (47 Basen vs. vorherige 12 Basen für starke Pseudoprimzahlen).
Kryptographische Implikationen: Obwohl der Miller-Rabin-Test (der in der Praxis häufiger verwendet wird) eine Fehlerwahrscheinlichkeit von maximal $1/4$ pro Basis hat und der Solovay-Strassen-Test $1/2$ , zeigt dieses Ergebnis, dass es möglich ist, zusammengesetzte Zahlen zu konstruieren, die für eine sehr lange Sequenz von Basen „unsichtbar" bleiben. Dies unterstreicht die Notwendigkeit, bei der Primzahlgenerierung entweder deterministische Tests zu verwenden oder eine sehr große Anzahl zufälliger Basen zu testen, insbesondere in adversarischen Szenarien.
Methodischer Beitrag: Die Arbeit liefert eine tiefgehende theoretische Klassifizierung von Carmichael-Zahlen und einen effizienten Algorithmus zur Konstruktion von Pseudoprimzahlen durch Multiplikation, der auf der Analyse der 2-adischen Bewertungen und der Jacobi-Symbole basiert.

Zusammenfassend beweisen die Autoren, dass die Suche nach „schlechten" Primzahlen (bzw. guten Pseudoprimzahlen) durch die systematische Nutzung der Eigenschaften von Carmichael-Zahlen der Klasse A und deren Multiplikation erheblich vorangetrieben werden kann.