Pseudoprimzahlen: Starke Pseudoprimzahlen

Aus Wikibooks

Inhaltsverzeichnis

1 die starke Pseudoprimzahl
2 starke Pseudoprimzahl und eulersche Pseudoprimzahl

[Bearbeiten] die starke Pseudoprimzahl

Um eine starke Pseudoprimzahl zu sein, muß eine zusammengesetzte Zahl $n = d\cdot 2^s+1\$ nur eine natürliche Zahl a zur Basis haben, für die entweder $a^d \equiv 1 \mod n$ oder $a^{d\cdot 2^r} \equiv -1 \mod n$ mit $0 \le r \le (s-1)$ gilt.

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 zeigen wird erstmal die Zerlegung gezeigt:

[Bearbeiten] Zerlegung

Gesucht wird das $d\$ zu einer Zahl $n\$ zu der Formel $n = d\cdot 2^s+1\$ . 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.

[Bearbeiten] 781 zur Basis 5

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

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

[Bearbeiten] 1541 zur Basis 5

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

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

[Bearbeiten] 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

[Bearbeiten] 305 zur Basis 11

Dies ist ein Gegenbeispiel.

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

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

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

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

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11

[Bearbeiten] starke Pseudoprimzahl und eulersche Pseudoprimzahl

Damit eine zusammengesetzte natürliche Zahl eine starke Pseudoprimzahl zur Basis $a\$ sein kann, muß sie auch eine eulersche Pseudoprimzahl zur Basis $a\$ sein. Warum? Für eine eulersche Pseudoprimzahl zur Basis $a\$ gilt $a^\frac{n-1}{2} \equiv 1 \mod n$ oder es gilt $a^\frac{n-1}{2} \equiv n-1 \mod n$ .

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