Das Kefk Network Wiki befindet sich im Testbetrieb.

Fermatsche Pseudoprimzahl

Aus Kefk.

Wechseln zu: Navigation, Suche

Die fermatsche Pseudoprimzahl n\ ist eine zusammengesetzte Zahl, die sich auf bestimmte Basen a\ mit \operatorname{ggT}(a,n)=1 und 2\le a\le n-2, wie eine Primzahl verhält.

Inhaltsverzeichnis

Vorbemerkung zur Kongruenz und zum Modulo

a \equiv b \; \pmod{c} wird „a ist kongruent zu b modulo c“ gesprochen.

Einleitung

Die fermatschen Pseudoprimzahlen lassen sich in zwei Mengen aufteilen: Einmal in die, die zugleich auch eulersche Pseudoprimzahlen sind, und solche die keine eulerschen Primzahlen sind. Zu den ersteren gehören die fermatschen Pseudoprimzahlen zur Basis 2, die Carmichael-Zahlen und absoluten eulerschen Pseudoprimzahlen. Die zweite Menge hat keine Relevanz.

{ absolute eulersche Primzahlen } \subset { Carmichael-Zahlen } \subset { eulersche Pseudoprimzahlen } \subset { fermatsche Pseudoprimzahlen }

Eigenschaften

  1. Eine fermatsche Pseudoprimzahl q\ ist mindestens zu einer Basis a\ mit a \ge 2\ pseudoprim.
  2. Wenn eine ungerade fermatsche Pseudoprimzahl q\ zu einer Basis a\ mit a < q\ pseudoprim ist, so ist q\ auch zu der Basis (q - a)\ pseudoprim.
  3. Wenn eine fermatsche Pseudoprimzahl q\ zu einer Basis a\ mit a < q\ pseudoprim ist, so ist q\ auch zu der Basis a^n\ mit einer natürlichen Zahl n \ge 1\ pseudoprim.
  4. Wenn eine fermatsche Pseudoprimzahl q\ zu einer Basis der Form a\ pseudoprim ist, so ist q\ auch pseudoprim zu einer Basis a + nq\ mit einer natürlichen Zahl n.
  5. Demzufolge ist eine fermatsche Pseudoprimzahl q\ zu jeder Basis b\ pseudoprim, zu der eine der folgenden drei Bedingungen zutrifft:
b \equiv a \mod q
b \equiv 1 \mod q
b \equiv (q-1) \mod q
Wobei a\ eine Basis sein muss, zu der q\ pseudoprim ist.

Beispiel: 15 ist eine fermatsche Pseudoprimzahl, die zu folgenden Basen Pseudoprim ist: 4, 11, 19, 26, ...

4^{14} \equiv 1 \mod 15 da 4 = 15-11\
19^{14} \equiv 1 \mod 15 da 19 \equiv 4 \mod 15
26^{14} \equiv 1 \mod 15 da 26 \equiv 11 \mod 15
...

Jede natürliche, zusammengesetzte Zahl n\ ist eine fermatsche Pseudoprimzahl zu Basen der Form m\cdot n+1 mit m \ge 1

(m\cdot n+1)^{n-1} \equiv 1 \mod n

Die Primzahl und der kleine Fermatsche Satz

Aus dem kleinen Fermatschen Satz folgt:

Wenn p eine Primzahl ist, dann gilt für alle natürlichen Zahlen a mit \operatorname{ggT}(a,p) = 1 und a > 1, dass a^{p-1} - 1 \equiv 0 \mod p ist. Oder anders ausgedrückt: Wenn p eine Primzahl ist, dann gilt für alle natürlichen Zahl a mit \operatorname{ggT}(a,p) = 1 und a > 1, dass ap − 1 − 1 durch p teilbar sein muss.


Beispiel p = 5

2 24 − 1 = 15 durch 5 teilbar
3 34 − 1 = 80 durch 5 teilbar
4 44 − 1 = 255 durch 5 teilbar

Definition

Eine (Fermatsche) Pseudoprimzahl ist eine zusammengesetzte, natürliche Zahl n, zu der mindestens eine natürliche Zahl a mit \operatorname{ggT}(a,n) = 1 und a > 1 existiert, so das:

a^{n-1} \equiv 1 \mod n, gilt.

Man sagt zu diesen Zahlen auch: "n ist pseudoprim zur Basis a".

Umgekehrt gaukelt die Basis a vor, das n eine Primzahl sei, obwohl sie es nicht ist. Die Basis lügt also.

Beispiel

Für die Zahl 91 gilt:

17 1790 − 1 ist durch 91 teilbar
29 2990 − 1 ist durch 91 teilbar
61 6190 − 1 ist durch 91 teilbar

Obwohl die 91 für bestimmte a (3, 17, 23, 29, 43, 53, 61 und 79) den kleinen Fermatschen Satz erfüllt, ist sie keine Primzahl.

Die kleinsten fermatschen Pseudoprimzahlen zu bestimmten Primbasen

Beispiele für kleinste Pseudoprimzahlen

kleinste Pseudoprimzahl zu den Basen
4 5
15 11
21 13
91 3
341 2
2701 2, 3
29341 2, 3, 5, 7, 11
162401 2, 3, 5, 7, 11, 13

Qualitative Unterschiede zwischen den Primzahlen, Carmichaelzahlen und Pseudoprimzahlen

Es gibt Abstufungen zwischen den Primzahlen, Carmichael-Zahlen und Pseudoprimzahlen. Diese Abstufungen kann man in Kriterien einteilen: Für eine Zahl n gilt: 

F1. Für alle a mit 2 \le a < n gilt, dass a^{n-1} \mod n = 1 ist.
F2. Für alle a mit 2 \le a < n und a teilerfremd zu n, gilt, dass a^{n-1} \mod n = 1 ist.
F3. Für manche a mit 2 \le a < n und a teilerfremd zu n, gilt, dass a^{n-1} \mod n = 1 ist.
E1. Für alle a mit 2 \le a < n gilt, dass a^{\frac{n-1}{2}} \mod n = 1 oder a^{\frac{n-1}{2}} \mod n = (n-1) ist.
E2. Für alle a mit 2 \le a < n und a teilerfremd zu n gilt, dass a^{\frac{n-1}{2}} \mod n = 1 oder a^{\frac{n-1}{2}} \mod n = (n-1) ist.
E3. Für manche a mit 2 \le a < n und a teilerfremd zu n gilt, dass a^{\frac{n-1}{2}} \mod n = 1 oder a^{\frac{n-1}{2}} \mod n = (n-1) ist.
E4. Für manche a mit 2 \le a < n und a teilerfremd zu n kann gelten, dass a^{\frac{n-1}{2}} \mod n = 1 oder a^{\frac{n-1}{2}} \mod n = (n-1) ist.
C1. λ(n) teilt n-1.
C2.  λ(n) teilt nicht n-1.
Primzahl F1. E1. C1.
Absolute Eulersche Pseudoprimzahl F2. E2. C1.
Carmichael-Zahl F2. E3. C1.
Eulersche Pseudoprimzahl F3. E3. C2.
Fermatsche Pseudoprimzahl F3. E4. C2.

Pseudoprimzahlen zur Basis a nach Michele Cipolla, 1904

Für ein a \ge 2 und eine ungerade Primzahl p, die a(a2 − 1) nicht teilt, bekommt man mit

n_1=\frac{a^p-1}{a-1} \ \ n_2=\frac{a^p+1}{a+1} \ \ n=n_1n_2

drei Zahlen n1, n2 und n, wobei n1 und n2 ungerade sind und n zusammengesetzt ist.

Aus n_1 \equiv 1 \mod 2p und n_2 \equiv 1 \mod 2p

folgt, dass auch n \equiv 1 \mod 2p ist.

Aus a^{2p} \equiv 1 \mod n

folgt, dass a^{n-1} \equiv 1 \mod n ist,

so dass n eine Pseudoprimzahl zur Basis a sein muss. Da es unendlich viele Primzahlen gibt, muss es demnach auch unendlich viele Pseudoprimzahlen geben.

a p n1 n2 n=n1*n2 Faktoren
2 5 31 11 341 11*31
2 7 127 43 5461 43*127
3 5 121 61 7381 11*11*61
3 7 1093 547 597871 547*1093
2 11 2047 683 1398101 23*89*683
7 5 2801 2101 5884901 11*191*2801
2 13 8191 2731 22369621 2731*8191
5 7 19531 13021 254313151 29*449*19531
13 5 30941 26521 809977861 11*2411*30941
3 11 88573 44287 3922632451 23*67*661*3851
2 17 131071 43691 5726623061 43691*131071
17 5 88741 78881 6999978821 11*71*101*88741
2 19 524287 174763 91625968981 174763*524287
3 13 797161 398581 317733228541 398581*797161
11 7 1948717 1623931 3164581946527 43*45319*1623931
2 23 8388608 2796203 23456248059221 47*178481*2796203


Pseudoprimzahlen der Form (6n+1)*(12n+1)

Ähnlich den Carmichael-Zahlen nach Chernick, die der Form (6n+1)*(12n+1)*(18n+1) entsprechen, scheinen die Pseudoprimzahlen der Form (6n+1)*(12n+1) eine besondere Bedeutung zu haben. Abgesehen von den Carmichael-Zahlen, haben sie die meisten Primbasen:

n 6n+112n+1(6n+1)*(12n+1)AaP AalP Ratio
1 7 13 91 24 8 33,33%
3 19 37 703 126 56 44,44%
5 31 61 1891 290 139 47,93%
6 37 73 2701 393 191 48,60%
13 79 157 12403 1480 739 49,93%
16 97 193 18721 2137 1070 50,07%

ApP = Anzahl aller Primzahlen kleiner als (6n+1)*(12n+1)

AalP = Anzahl der lügenden Primzahlbasen*

* Primzahlen, die fälschlicherweise den Anschein erwecken, die zu testende Zahl (6n+1)*(12n+1) sei eine Primzahl

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!
  • The New Book of Prime Number Records, Paolo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5
  • Prime Numbers - A Computational Cerspective, Second Edition, Richard Crandall & Carl Pomerance, Springer Verlag 2005, ISBN 0-387-25282-7

siehe auch

Weblinks

Von „http://www.kefk.org/wiki/Fermatsche_Pseudoprimzahl“
Persönliche Werkzeuge