Das Kefk Network Wiki befindet sich im Testbetrieb.

Eulersche Pseudoprimzahl

Aus Kefk.

Wechseln zu: Navigation, Suche

Die Menge der Eulerschen Pseudoprimzahlen ist eine Teilmenge der fermatschen Pseudoprimzahlen.


Inhaltsverzeichnis

Definition einer Eulerschen Pseudoprimzahl

Vorbemerkung zur Kongruenz und zum Modulo

a \equiv b \mod c wird "a ist kongruent zu b modulo c" gesprochen.

Definition

Es gibt in der Literatur zwei leicht unterschiedliche Varianten, den Begriff eulersche Pseudoprimzahl zu definieren.

"Einfache" eulersche Pseudoprimzahlen

Eine ungerade zusammengesetzte natürliche Zahl n wird eine eulersche Pseudoprimzahl zur Basis a genannt, wenn entweder

  • a^{\frac{n-1}{2}} \equiv 1 \mod n

oder

  • a^{\frac{n-1}{2}} \equiv -1 \mod n

gilt.[1]

Euler-Jacobi-Pseudoprimzahlen

Eine ungerade, zusammengesetzte Zahl n wird eine eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd sind und

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

gilt[2]; dabei bezeichnet \left(\frac an\right) das Jacobi-Symbol. Zur Unterscheidung von der ersten Definition spricht man auch von Euler-Jacobi-Pseudoprimzahlen[3]

Vergleich

Offenbar impliziert die zweite Variante die erste, 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.

Die Eulersche Formel und der kleine Fermatsche Satz

Eine Eulersche Pseudoprimzahl ist auch eine Fermatsche Pseudoprimzahl

Aus

a^{\frac{n-1}{2}} \cdot a^{\frac{n-1}{2}} = (a^{\frac{n-1}{2}})^2 = a^{2\cdot \frac{n-1}{2}} = a^{n-1}

und

1 \cdot 1 = (-1) \cdot (-1) = 1

folgt, dass wenn n eine Eulersche Pseudoprimzahl ist, n auch eine Fermatsche Pseudoprimzahl sein muss.

Da es aber auch möglich sein kann, dass es für a^{\frac{n-1}{2}} \mod n einen Rest geben kann, der nicht 1 oder (n-1) ist, aber dennoch zum Quadrat als Rest ein 1 Mod n zurückliefert, kann man nicht sagen, dass wenn n eine Fermatsche Pseudoprimzahl ist, sie auch zwangsläufig eine Eulersche Pseudoprimzahl sein muss.

Eine Fermatsche Pseudoprimzahl muss keine Eulersche Pseudoprimzahl sein

Ein Beispiel für eine Fermatsche Pseudoprimzahl, die keine Eulersche Pseudoprimzahl ist, ist die Zahl 15:

11^{14} \equiv 1 \mod 15

aber

11^7 \equiv 11 \mod 15

da 112 = 121, und 121 \equiv 1 \mod 15 ist, ergibt sich daraus kein Widerspruch.

Arten von eulerschen Pseudoprimzahlen

Pseudoprimzahlen nach Fermat zur Basis 2 (Poulet-Zahl)

Eine Poulet-Zahl ist eine fermatsche Pseudoprimzahl zur Basis 2.

341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033
4369 4371 4681 5461 6601 7957 8321 8481 8911 10261 10585 11305 12801
13741 13747 13981 14491 15709 15841 16705 18705 18721 19951 23001 23377 25761
29341 30121 30889 31417 31609 31621 33153 34945 35333 39865 41041 41665 42799
46657 49141 49981 52633 55245 57421 60701 60787 62745 63973 65077 65281 68101
72885 74665 75361 80581 83333 83665 85489 87249 88357 88561 90751 91001 93961
101101 104653 107185 113201 115921 121465 123251 126217 129889 129921 130561 137149 149281
150851 154101 157641 158369 162193 162401 164737 172081 176149 181901 188057 188461 194221
196021 196093 204001 206601 208465 212421 215265 215749 219781 220729 223345 226801 228241
233017 241001 249841 252601 253241 256999 258511 264773 266305 271951 272251 272251 275887

Alle Pseudoprimzahlen nach Fermat zur Basis 2 (von 341 bis 275887). Die fett gedruckten Zahlen sind Carmichaelzahlen.

Die Zahl 341 als Pseudoprimzahl zur Basis 2 wurde 1819 von P.F.Sarrus entdeckt.

Carmichael-Zahlen

Eine Carmichael-Zahl ist eine fermatsche Pseudoprimzahl, die zu jeder teilerfremden Basis pseudoprim ist. Carmichael-Zahlen, die zu allen teilerfremden Basen eine eulersche Pseudoprimzahl darstellen, nennt man absolute eulersche Pseudoprimzahlen.

starke Pseudoprimzahlen

Literatur

  • Carl Pomerance: The Search for Prime Numbers in: Scientific American, December 1982
  • Carl Pomerance: Primzahlen im Schnelltest in: Spektrum der Wissenschaft, Februar 1983 S. 80-92. (Es handelt sich um die Übersetzung des vorerwähnten Artikels) mit Foto eines Nachbaus von Lehmers Fahrradkettencomputers von 1926!
  • Paolo Ribenboim, The New Book of Prime Number Records, Springer-Verlag 1996, ISBN 0-387-94457-5
  • Neil Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag 1994. ISBN 0-387-94293-9/ISBN 3-540-94293-9

Quellen

  1. ↑ Eric W. Weisstein. "Euler Pseudoprime." From MathWorld--A Wolfram Web Resource.
  2. ↑ Koblitz, a.a.O., S. 129; Ribenboim, a.a.O., S. 112; Y. I. Manin, A. A. Panchishkin, Introduction to Modern Number Theory, Springer-Verlag 2005. ISBN 3-540-20364-8, S. 16
  3. ↑ Eric W. Weisstein. "Euler-Jacobi Pseudoprime." From MathWorld--A Wolfram Web Resource.

Weblinks

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