Eulersche Pseudoprimzahl

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

Inhaltsverzeichnis

1 Definition einer Eulerschen Pseudoprimzahl
- 1.1 Vorbemerkung zur Kongruenz und zum Modulo
- 1.2 Definition
2 Die Eulersche Formel und der kleine Fermatsche Satz
- 2.1 Eine Eulersche Pseudoprimzahl ist auch eine Fermatsche Pseudoprimzahl
- 2.2 Eine Fermatsche Pseudoprimzahl muss keine Eulersche Pseudoprimzahl sein
3 Arten von eulerschen Pseudoprimzahlen
4 Literatur
5 Quellen
6 Weblinks

[Bearbeiten] Definition einer Eulerschen Pseudoprimzahl

[Bearbeiten] Vorbemerkung zur Kongruenz und zum Modulo

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

[Bearbeiten] Definition

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

[Bearbeiten] "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]

[Bearbeiten] 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]

[Bearbeiten] 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.

[Bearbeiten] Die Eulersche Formel und der kleine Fermatsche Satz

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] Arten von eulerschen Pseudoprimzahlen

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] starke Pseudoprimzahlen

[Bearbeiten] 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