Pseudoprimzahlen: Starke Pseudoprimzahlen

Vorlage:Navigation Buch Jede ungerade Primzahl $n$ erfüllt mit jeder teilerfremden ganzzahligen Basis $a$ eine der Kongruenzen Vorlage:Formel2 Vorlage:Formel2. Anmerkung: Kongruenz (2) ist gleichbedeutend mit $a^{d \cdot 2^{r}} \equiv n - 1 (\mod 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 (\mod 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^[1] 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.^[2]

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

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 (\mod 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 (\mod n)$ gilt, gilt auch $(a^{d})^{2^{s - 1}} \equiv \pm 1 (\mod n)$ und damit auch $a^{\frac{n - 1}{2}} = a^{d \cdot 2^{s - 1}} \equiv \pm 1 (\mod 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 (\mod n)$ ist also eine der obengenannten Kongruenzen erfüllt.

Teiler

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

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

wobei $l_{a} (p)$ die multiplikative Ordnung von $p$ zur Basis $a$ ist.^[4] ^[5]^[6]

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}$ ).^[7]

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 ℕ

,

\gcd (k, m) = 1

und

0 < k ≪ q, 0 < m ≪ 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}^{'}$ der größte ungerade Teiler von $p_{i} - 1$ ,
$ν_{2} (p_{i})$ der größte Exponent, mit dem $2^{ν_{2} (p_{i})} | p_{i} - 1$ gilt, so dass $p_{i} - 1 = 2^{ν_{2} (p_{i})} \cdot p_{i}^{'}$ ist und
$ν$ das Minimum aller $ν_{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^[8]	Fermatsche Pseudoprimzahlen	Starke Pseudoprimzahlen^[9]
$1 0^{9}$	50.847.534	5.597	1.282
$1 0^{12}$	37.607.912.018	101.629	22.407
$1 0^{15}$	29.844.570.422.669	1.801.533	419.489
$1 0^{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 (\mod 781)$ also ist 781 eine starke Pseudoprimzahl zur Basis 5.

1541 zur Basis 5

$n = 1541 d = 385$

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

25 zur Basis 7

$n = 25 d = 3$

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

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

305 zur Basis 11

Dies ist ein Gegenbeispiel.

$n = 305 d = 19$

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

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

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

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11.

Quellen

↑ Vorlage:W
↑ Vorlage:W
↑ Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7 http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf
↑ The pseudoprimes to 25 * 10^9
↑ Glossar
↑ Vorlage:W
↑ New Implementations for Tabulating Pseudoprimes and Liars.pdf
↑ Vorlage:W
↑ Pseudoprimzahlen: Vorlage:Statistics

Vorlage:Navigation Text

[1] Vorlage:W

[2] Vorlage:W

[3] Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7 http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf

[4] The pseudoprimes to 25 * 10^9

[5] Glossar

[6] Vorlage:W

[7] New Implementations for Tabulating Pseudoprimes and Liars.pdf

[8] Vorlage:W

[9] Pseudoprimzahlen: Vorlage:Statistics

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Pseudoprimzahlen: Starke Pseudoprimzahlen

Inhaltsverzeichnis

Definition

Eigenschaften

Bezug zu Eulerschen Pseudoprimzahlen

Teiler

Anzahl der Basen

Häufigkeit

Restklassen

Beispiele

Quellen

Navigationsmenü

Pseudoprimzahlen: Starke Pseudoprimzahlen

Definition

Eigenschaften

Bezug zu Eulerschen Pseudoprimzahlen

Teiler

Anzahl der Basen

Häufigkeit

Restklassen

Beispiele

Quellen

Navigationsmenü

Suche