Das Kefk Network Wiki befindet sich im Testbetrieb.

Starke Pseudoprimzahl

Aus Kefk.

Wechseln zu: Navigation, Suche

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

Inhaltsverzeichnis

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)

Beispiele

341 = 85*22+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

Anwendung der starken Pseudoprimzahlen

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

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.

Von „http://www.kefk.org/wiki/Starke_Pseudoprimzahl“
Persönliche Werkzeuge
Andere Sprachen