Eulersche Pseudoprimzahl - LinkFang.de





Eulersche Pseudoprimzahl


Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz

[math]a^\frac{n-1}{2} \equiv \pm 1 \mod n[/math]

erfüllt ist.

Anders ausgedrückt muss n die Differenz [math]a^\frac{n-1}{2}-1[/math] oder die Summe [math]a^\frac{n-1}{2}+1[/math] teilen.

Eine Folgerung aus dem kleinen fermatschen Satz

Eine eulersche Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf eine Folgerung aus dem kleinen Fermatschen Satz:

ist p eine ungerade Primzahl, so teilt sie [math]a^{p-1}-1[/math], also auch einen der beiden Faktoren [math](a^\frac{p-1}{2}+1)(a^\frac{p-1}{2}-1)[/math] (dritte Binomische Formel). Beispielsweise ist 7 ein Teiler von 36-1 = 728 = 26·28, und einer der Faktoren ist durch 7 teilbar. Dieses Kriterium lässt sich für Primzahltests verwenden. Wie üblich nennt man die zusammengesetzten Zahlen, die das Kriterium erfüllen, Pseudoprimzahlen (in Bezug auf die betrachtete Eigenschaft).

Jede eulersche Pseudoprimzahl ist eine fermatsche Pseudoprimzahl (man quadriere beide Seiten der Kongruenz). Sie sind nach Leonhard Euler benannt.

Definition

Es gibt zwei Varianten, den Begriff eulersche Pseudoprimzahl zu definieren. Beide Fälle setzen voraus, dass die Basis a teilerfremd zu n ist.

Eulersche Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl [math]n[/math] heißt eulersche Pseudoprimzahl zur Basis a, wenn

[math]a^{\frac{n-1}{2}} \equiv \pm 1 \mod n[/math]

gilt.[1]

Euler-Jacobi-Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl [math]n[/math] heißt Euler-Jacobi-Pseudoprimzahl zur Basis a, wenn

[math]a^{(n-1)/2} \equiv \left(\frac an\right)\mod n[/math]

gilt. Dabei bezeichnet [math]\left(\frac an\right)[/math] das Jacobi-Symbol.[2]
Für prime n wird diese Eigenschaft eulersches Kriterium (für das Legendre-Symbol) genannt; es gilt nämlich für alle Primzahlen p > 2:

[math]a^{(p-1)/2} \equiv \left(\frac ap\right)\mod p[/math] .

Vergleich

Offenbar impliziert die zweite Variante die erste (da für teilerfremde a und n das Jacobi-Symbol die Werte +1 und -1 annimmt). Die Beispiele n = 341, a = 2 oder n = 21, a = 8 zeigen, dass die Umkehrung falsch ist. Die zweite Definition ist also echt stärker. Das Vorgehen der zweiten Definition ist die Basis des Solovay-Strassen-Tests.

Eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist

Die Zahl n = 15 liefert mit der Basis a = 11 ein Beispiel für eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist:

Es gilt:

[math]11^{14} \equiv 1 \mod 15[/math] ,

aber

[math]11^7 \equiv 11 \mod 15[/math] ;

Man beachte:

[math]11^2 = 121 \equiv 1 \mod 15[/math] .

Absolute eulersche Pseudoprimzahlen

Zahlen, die zu allen teilerfremden Basen eine eulersche Pseudoprimzahl darstellen, nennt man absolute eulersche Pseudoprimzahlen.

Literatur

  • Neil Koblitz: A Course in Number Theory and Cryptography. 2nd edition. Springer, New York NY u. a. 1994, ISBN 3-540-96576-9 (Graduate Texts in Mathematics 114).

sowie die in Pseudoprimzahl angegebene Literatur.

Siehe auch

Einzelnachweise

  1. Eric W. Weisstein: "Euler Pseudoprime." (MathWorld)
  2. Eric W. Weisstein: "Euler-Jacobi Pseudoprime." (MathWorld)

Kategorien: Primzahl

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Eulersche Pseudoprimzahl (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.