Starke Pseudoprimzahl

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Eine starke Pseudoprimzahl zur Basis a ist eine eulersche Pseudoprimzahl zur Basis a. Allerdings ist nicht jede eulersche Pseudoprimzahl eine starke Pseudoprimzahl.

Inhaltsverzeichnis

1 Definition
2 Beispiele
3 Anwendung der starken Pseudoprimzahlen
4 Warum eine starke Pseudoprimzahl auch eine eulersche Pseudoprimzahl sein muss

[Bearbeiten] Definition

Eine zusammengesetze Zahl $n = d \cdot 2^s+1$ ist dann eine starke Pseudoprimzahl zur Basis a , wenn genau eine der zwei folgenden Bedingungen erfüllt ist:

$a^d \equiv 1 \mod n$

$a^{d \cdot 2^r} \equiv -1 \mod n$ mit $0 \le r \le (s-1)$

[Bearbeiten] Beispiele

341 = 85*2²+1

341 ist eine starke Pseudoprimzahl zur Basis 47, da $47^{85} \equiv 1 \mod 341$

341 ist auch eine starke Pseudoprimzahl zur Basis 61, da $61^{85 \cdot 2^0} \equiv 340 \mod 341$

[Bearbeiten] Anwendung der starken Pseudoprimzahlen

Der Miller-Rabin-Test nutzt die Eigenschaften der starken Pseudoprimzahlen zur schnellen Bestimmung von Zahlen, die wahrscheinlich prim sind.

[Bearbeiten] Warum eine starke Pseudoprimzahl auch eine eulersche Pseudoprimzahl sein muss

Eine eulersche Pseudoprimzahl ist eine zusammengesetzte Zahl, die eine der beiden folgenden Bedingungen erfüllt: $a^{\frac{n-1}{2}} \equiv 1 \mod n$ oder $a^{\frac{n-1}{2}} \equiv -1 \mod n$ bzw. $a^{\frac{n-1}{2}} \equiv (n-1) \mod n$ .

Beschränken wir uns vorläufig auf $a^{\frac{n-1}{2}} \equiv 1 \mod n$ . Dabei gilt, das $a^{\frac{n-1}{2}} = a^{d\cdot 2^{s-1}}$ ist. Das bedeutet, das wenn die Bedingung $a^d \equiv 1 \mod n$ erfüllt ist, automatisch auch die Bedingung $(a^d)^{2^{s-1}} \equiv 1 \mod n = a^{d\cdot 2^{s-1}} \equiv 1 \mod n$ erfüllt ist. Eine starke Pseudoprimzahl, die Bedingung 1 erfüllt, muss also auch eine eulersche Pseudoprimzahl sein.

Was ist mit Bedingung 2? Wenn $a^{\frac{n-1}{2}} = a^{d\cdot 2^0}$ ist, und $a^{d\cdot 2^r} \equiv -1 \mod n$ mit $0 \le r \le (s-1)$ gilt, dann gilt auch $a^{\frac{n-1}{2}} \equiv -1 \mod n$ .