Pseudoprimzahlen: Starke Pseudoprimzahlen

Pseudoprimzahlen

Jede ungerade Primzahl $n$ erfüllt mit jeder teilerfremden ganzzahligen Basis $a$ eine der Kongruenzen

$a^{d}\equiv 1{\pmod {n}}\quad$mit $\ n-1=d\cdot 2^{s}\$ und $d\$ ungerade

(1)

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

(2)

. Anmerkung: Kongruenz (2) ist gleichbedeutend mit $a^{d\cdot 2^{r}}\equiv n-1{\pmod {n}}$.

Definition

Eine ungerade Zahl $n$ ist starke Pseudoprimzahl zur Basis $a$, wenn sie zusammengesetzt ist, und mit einer ganzzahligen Basis $a$, für die $1<a<n-1{\pmod {n}}$ gilt, eine der obengenannten Kongruenzen erfüllt ist. In dieser Hinsicht verhält sie sich wie eine Primzahl.

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 ($2^{p}-1$ mit $\ p$ = prim) sind starke Pseudoprimzahlen zur Basis 2.

Alle zusammengesetzten Fermatzahlen ($2^{2^{n}}+1$) sind starke Pseudoprimzahlen zur Basis 2.

$(4^{p}+1)/5$ ist starke Pseudoprimzahl zur Basis 2, wenn $p>5$ und eine Primzahl ist.

Die Quadrate der Wieferich-Primzahlen 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 \pm 1{\pmod {n}}$.

$a^{\frac {n-1}{2}}$ lässt sich auch als $a^{d\cdot 2^{s-1}}$ schreiben. Wenn nun $a^{d}\equiv \pm 1{\pmod {n}}$ gilt, gilt auch $(a^{d})^{2^{s-1}}\equiv \pm 1{\pmod {n}}$ und damit auch $a^{\frac {n-1}{2}}=a^{d\cdot 2^{s-1}}\equiv \pm 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}}$; mit $\ a^{\frac {n-1}{2}}\equiv \pm 1{\pmod {n}}\$ ist also eine der obengenannten Kongruenzen erfüllt.

Teiler

Für alle Primteiler $p$ einer starken Pseudoprimzahl $n\$gilt

• $n\equiv 1{\pmod {l_{a}(p)}}$ und damit
• $n\equiv p{\pmod {p\cdot l_{a}(p)}}$,

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 starken 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).

Starke Pseudoprimzahlen lassen sich häufig als Produkte der Form

$\ q=(2\cdot k\cdot x+1)\cdot (2\cdot m\cdot x+1)\$ mit

$\quad x\in \mathbb {N}$,

$\quad \gcd(k,m)=1\$und

$\quad 0<k\ll q,\ 0<m\ll q\$

ausdrücken. Umgekehrt ist der Anteil starker Pseudoprimzahlen bei solchen Produkten deutlich höher als bei ungeraden Zahlen allgemein.

Anzahl der Basen

Wenn die Primteiler$\ p_{i}\$einer zusammengesetzten Zahl $n$ bekannt sind, kann die Anzahl der Basen, zu denen sie starke Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

$n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}$

ist die Anzahl der Basen $<n$ einschließlich 1 und n-1

$\left(1+{\frac {2^{k\nu }-1}{2^{k}-1}}\right)\prod _{i=1}^{k}\gcd \left(d,\ p_{i}^{'}\right)$

Dabei ist

• $\ d$ der größte ungerade Teiler von $\ n-1$ (wie oben)
• $\ p_{i}^{'}$ der größte ungerade Teiler von $\ p_{i}-1$,
• $\ \nu _{2}(p_{i})$ der größte Exponent, mit dem $\ 2^{\nu _{2}(p_{i})}|p_{i}-1\$gilt, so dass $\ p_{i}-1=2^{\nu _{2}(p_{i})}\cdot p_{i}^{'}\$ist und
• $\ \nu$ das Minimum aller $\nu _{2}(p_{i})$.

Basen, zu denen eine zusammengesetze Zahl $n\$keine Pseudoprimzahl ist, werden Zeugen für die Zusammengesetztheit der Zahl genannt; solche zu denen sie pseudoprim ist, werden „falsche Zeugen“ genannt. Maximal ein Viertel der teilerfremden Basen zwischen 0 und n sind falsche Zeugen.

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
$10^{18}$	24.739.954.287.740.860	33.763.684	8.646.507

Restklassen

Starke Pseudoprimzahlen liegen wesentlich häufiger in der Restklasse 1 modulo kleiner Zahlen $(m)$ als in anderen Restklassen. Folgende Tabelle zeigt die Verteilung der starken Pseudoprimzahlen zur Basis 2 bis 10¹⁵ auf Restklassen modulo m an ein paar Beispielen.

	Anzahl starker Pseudoprimzahlen zur Basis 2 in Restklasse
m	0	1	2	3	4	5	6	7
3	26	327193	92270
5	1373	199879	84716	74590	58931
7	370	142844	49224	62834	47482	57853	58882
8	0	207103	0	44885	0	122473	0	45028

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.