Pseudoprimzahlen: Starke Pseudoprimzahlen

Pseudoprimzahlen

Definition

Eine ungerade Zahl $n$ wird starke Pseudoprimzahl genannt, wenn sie zusammengesetzt ist, und mit einer ganzzahligen Basis $a$, für die $1<a<n-1{\pmod {n}}$ gilt, eine der Kongruenzen

• $a^{d}\equiv 1{\pmod {n}}\quad$mit $n=d\cdot 2^{s}+1$ und $d$ ungerade
• $a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad$für ein $r$ mit $0\leqq r<s$

erfüllt ist. In dieser Hinsicht verhält sich $n$ wie eine Primzahl und ist damit starke Pseudoprimzahl zur Basis $a$.

Die obengenannten Kongruenzen werden im Miller-Rabin-Test genutzt, um zu prüfen ob eine ungerade Zahl (wahrscheinlich) eine Primzahl oder sicher keine ist; dabei kann durch Tests mit mehreren Basen die Wahrscheinlichkeit, dass eine Pseudoprimzahl den Test besteht, reduziert werden.

Eigenschaften

Im Gegensatz zu den fermatschen Pseudoprimzahlen gibt es keine starken Pseudoprimzahlen, die zu jeder teilerfremden Basis pseudoprim sind; eine Entsprechung zu den Carmichael-Zahlen gibt es also nicht.

Alle zusammengesetzten Mersennezahlen sind starke Pseudoprimzahlen zur Basis 2.

Alle zusammengesetzten Fermatzahlen sind starke Pseudoprimzahlen zur Basis 2.

Bezug zu Eulerschen Pseudoprimzahlen

Jede starke Pseudoprimzahl $n\$ zur Basis $a\$ ist auch eine Eulersche Pseudoprimzahl zur Basis $a\$. Warum? Für eine eulersche Pseudoprimzahl zur Basis $a\$ gilt $a^{\frac {n-1}{2}}\equiv 1{\pmod {n}}$ oder es gilt $a^{\frac {n-1}{2}}\equiv n-1{\pmod {n}}$ .

$a^{\frac {n-1}{2}}$ lässt sich auch als $a^{d\cdot 2^{s-1}}$ schreiben. Wenn nun für $n\$ zur Basis $a\$ nun $a^{d}\equiv 1{\pmod {n}}$ gilt, gilt auch $(a^{d})^{2^{s-1}}\equiv 1{\pmod {n}}$ und damit auch $a^{d\cdot 2^{s-1}}\equiv 1{\pmod {n}}$.

Jede eulersche Pseudoprimzahl der Form $\ n=4\cdot k+3\$ ist starke Pseudoprimzahl:
in diesem Fall ist $\ d={\frac {n-1}{2}}$ und $\ s=1\$ und damit $\ a^{d}=a^{\frac {n-1}{2}}=a^{d\cdot 2^{r}}$; wenn also $\ a^{\frac {n-1}{2}}\equiv \pm 1{\pmod {n}}\$ ist, ist eine der obengenannten Kongruenzen erfüllt.

Teiler

Wenn eine starke Pseudoprimzahl $n$ zur Basis $a$ durch die Primzahl $p$ teilbar ist, gilt $n\equiv p{\pmod {n\cdot l_{a}(n)}}$, wobei $l_{a}(p)$ die multiplikative Ordnung von $p$ zur Basis $a$ ist.

Die höchste Zweierpotenz, durch die die multiplikative Ordnung eines Primteilers teilbar ist, ist für alle Teiler einer Pseudoprimzahl gleich, d. h. alle multiplikativen Ordnungen der Primteiler derselben starken Pseudoprimzahl sind Produkt einer ungeraden Zahl und derselben Zweierpotenz (einschließlich $2^{0}$).

Starke Pseudoprimzahlen sind weitgehend quadratfrei; nur die Quadrate der Wieferich-Primzahlen zur Basis $a$ sind starke Pseudoprimzahlen zur Basis $a$ und können Teiler einer solchen sein. Mit der Basis 2 sind das die Wieferich-Primzahlen 1093 und 3511 (weitere sind bisher nicht bekannt).

Häufigkeit

Starke Pseudoprimzahlen zu einer festen Basis sind viel seltener als Primzahlen. Folgende Tabelle zeigt die Anzahl starker Pseudoprimzahlen zur Basis 2 im Vergleich zur Anzahl fermatscher Pseudoprimzahlen zur Basis 2 und der Primzahlen bis zur angegebenen Obergrenze.

Anzahl Starker Pseudoprimzahlen zur Basis 2 im Vergleich zu Primzahlen

Obergrenze	Primzahlen	Fermatsche Pseudoprimzahlen	Starke Pseudoprimzahlen
$10^{9}$	50.847.534	5.597	1.282
$10^{12}$	37.607.912.018	101.629	22.407
$10^{15}$	29.844.570.422.669	1.801.533	419.489

Beispiele

Um zu zeigen, wie unterschiedlich starke Pseudoprimzahlen ausfallen können, werden als Beispiele die drei Zahlen 781, 1541 und 25 gezeigt. An der Zahl 781 wird erstmal die Zerlegung gezeigt:

Zerlegung

Gesucht wird das $d\$ zu einer Zahl $n\$ so dass $n=d\cdot 2^{s}+1\$ mit ungeradem $d\$ gilt. Die Formel können wir umstellen:

• $n=d\cdot 2^{s}+1$
• $n-1=d\cdot 2^{s}$
• ${\frac {n-1}{2^{s}}}=d$

Am Beispiel der Zahl 781 sieht das so aus: Die Primfaktorzerlegung von $781-1=2^{2}\cdot 3\cdot 5\cdot 13\$. Wenn man die 2er-Potenzen entfernt, bleibt für $n=781\$ das $d=3\cdot 5\cdot 13=195\$ übrig.

781 zur Basis 5

$n=781\ \ \ d=195\$

$5^{195}\equiv 1{\pmod {781}}$ also ist 781 eine starke Pseudoprimzahl zur Basis 5.

1541 zur Basis 5

$n=1541\ \ \ d=385\$

$5^{385}\equiv 1540{\pmod {1541}}$ also ist 1541 eine starke Pseudoprimzahl zur Basis 5.

25 zur Basis 7

$n=25\ \ \ d=3\$

$7^{3}\equiv 18{\pmod {25}}$

$7^{6}\equiv 24{\pmod {25}}$ also ist 25 eine starke Pseudoprimzahl zur Basis 7.

305 zur Basis 11

Dies ist ein Gegenbeispiel.

$n=305\ \ \ d=19\$

$11^{19}\equiv 111{\pmod {305}}$

$11^{38}\equiv 121{\pmod {305}}$

$11^{76}\equiv 1{\pmod {305}}$

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11.