Pseudoprimzahlen: Starke Pseudoprimzahlen

Vorlage:Navigation Buch Jede ungerade Primzahl $n$ erfüllt mit jeder teilerfremden ganzzahligen Basis $a$ eine der Kongruenzen Vorlage:Formel2Vorlage:Formel2 Anmerkung: Kongruenz (2) ist gleichbedeutend mit $a^{d\cdot 2^r}\equiv n-1(\mathrm{mod}n)$.

Jedes Folgeglied der Folge $a_r=a^{d\cdot 2^r}$ ist das Quadrat (mod n) des vorangehenden. Wenn $a_r=a^{d\cdot 2^r}\equiv ̸-1(\mathrm{mod}n)$ ist und $a_{r+1}=(a^{d\cdot 2^r}{)}^2\equiv 1(\mathrm{mod}n)$ ist, kann $n$ keine Primzahl sein, weil die Gleichung $x^2\equiv 1(\mathrm{mod}n)$ nur die Lösungen $x=\pm 1(\mathrm{mod}n)$ hat, wenn n eine Primzahl ist. In diesem Fall ist $a_r^2-1=(a_r+1)\cdot (a_r-1)\equiv 0(\mathrm{mod}n)$, das Produkt $(a_r+1)\cdot (a_r-1)$ ist also durch $n$ teilbar, und $gcd(a_r+1,n),gcd(a_r-1,n)$ sind Teiler von $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(\mathrm{mod}n)$ gilt, eine der obengenannten Kongruenzen erfüllt ist. In dieser Hinsicht verhält sie sich wie eine Primzahl.
Mit $a=1$ erfüllen alle ganzen Zahlen Kongruenz (1) und mit $a=n-1$ alle ungeraden Zahlen Kongruenz (2), solche Basen eignen sich also nicht zur Erkennung zusammengesetzter Zahlen.

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. Starke Pseudoprimzahlen zur Basis $a$ sind also zusammengesetzte Zahlen, die den Miller-Rabin-Test mit der Basis $a$ bestehen.

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, und es ist auch nicht jede zusammengesetzte ungerade Zahl starke Pseudoprimzahl zu irgendeiner Basis 1 < a < n-1.

• 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(\mathrm{mod}n)$. Mit der oben beschriebenen Zerlegung $n-1=d\cdot 2^s$ ist $a^{\frac{n-1}{2}}=a^{d\cdot 2^{s-1}}$.

Bei starken Pseudoprimzahlen gibt es zwei Fälle:

1. Kongruenz 1 ist erfüllt: $a^d\equiv 1(\mathrm{mod}n)$,
   dann ist $a^{d\cdot 2^{s-1}}=(a^d{)}^{2^{s-1}}\equiv 1^{2^{s-1}}(\mathrm{mod}n)=1$ und damit $a^{\frac{n-1}{2}}\equiv 1(\mathrm{mod}n)$.
2. Kongruenz 2 ist erfüllt: $a^{d\cdot 2^r}\equiv -1(\mathrm{mod}n)$,
   dann ist $a^{d\cdot 2^{s-1}}=(a^{d\cdot 2^r}{)}^{2^{s-r-1}}\equiv (-1{)}^{2^{s-r-1}}(\mathrm{mod}n)\equiv \pm 1$ und damit $a^{\frac{n-1}{2}}\equiv \pm 1(\mathrm{mod}n)$.

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

Teiler

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

• $n\equiv 1(\mathrm{mod}{l}_a(p))$ und damit
• $n\equiv p(\mathrm{mod}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

$x\in \mathbb{N}$,

$gcd(k,m)=1$und

$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 Vorlage:Formel2 ist die Anzahl der Basen $<n$ einschließlich 1 und n-1 Vorlage:Formel2

Dabei ist

• $d$ der größte ungerade Teiler von $n-1$ (wie oben)
• $p_i^{\text{'}}$ 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^{\text{'}}$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 in eine 2er-Potenz und eine ungerade Zahl gezeigt:

Zerlegung

Zu einer Zahl $n$ wird das ungerade $d$ gesucht, so dass $n=d\cdot 2^s+1$ 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 $n=781$ sieht das so aus: Die größte 2er-Potenz, durch die $n-1=780$ teilbar ist, ist $2^2=4$; der andere Faktor ist dann $d=780/4=195$. Es wird also nicht die vollständige Primfaktorzerlegung $781-1=2^2\cdot 3\cdot 5\cdot 13$ gebraucht.

781 zur Basis 5

$a=5$

$n=781d=195$

$5^{195}\equiv 1(\mathrm{mod}781)$ also ist 781 eine starke Pseudoprimzahl zur Basis 5.

1541 zur Basis 5

$a=5$

$n=1541d=385$

$5^{385}\equiv 1540(\mathrm{mod}1541)$ also ist 1541 eine starke Pseudoprimzahl zur Basis 5.

25 zur Basis 7

$a=7$

$n=25d=3$

$7^3\equiv 18(\mathrm{mod}25)$

$7^6\equiv 24(\mathrm{mod}25)$ also ist 25 eine starke Pseudoprimzahl zur Basis 7.

305 zur Basis 11

Dies ist ein Gegenbeispiel.

$a=11$

$n=305d=19$

$11^{19}\equiv 111(\mathrm{mod}305)$

$11^{38}\equiv 121(\mathrm{mod}305)$

$11^{76}\equiv 1(\mathrm{mod}305)$

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11. Aus $121^2\equiv 1(\mathrm{mod}305)$ kann auf die Teiler $gcd(121+1,305)=5$ und $gcd(121-1,305)=61$ geschlossen werden (in diesem Fall sind es Primteiler).

Quellen

Vorlage:Navigation Text