Pseudoprimzahlen: Meta: Überblick

Vorwort

Was soll das Buch bezwecken?

Das Buch soll das zeigen, was jenseits der Primzahlen kommt. Die faszinierende Welt der Pseudoprimzahlen.

Warum dieses Buch?

In der deutschen Wikipedia sind einige interessante Artikel über den Bereich Pseudoprimzahlen, Primzahlen und Randbereiche entstanden. So die Artikel Carmichael-Zahl, Eulersche Pseudoprimzahl, Starke Pseudoprimzahl, Lucas-Folge u.s.w. . Nun ist die Wikipedia ja eine Enzyklopädie und kein Lehrbuch, was bedeutet, dass man weder in die Tiefe gehen kann, noch Zusammenhänge so vernetzen kann, wie man das gerne möchte.

Für wen ist dieses Buch gedacht?

Dieses Buch ist für jene gedacht, die gerne tüfteln. Der Stoff ist vielleicht nicht einfach zugänglich, aber wer eine gewisse Hürde übersprungen hat, für den eröffnen sich Welten (auch in Bezug auf die Primzahlen). Was dieses Buch nicht ist, ist ein Lehrbuch, das den Leser von Punkt zu Punkt führt. Der Leser muß sich seine Ziele selber suchen. Wer sich nicht schon für die natürlichen Zahlen, und insbesondere für Primzahlen interessiert, der wird mit diesem Lehrbuch wenig Freude haben.

Ein rechenintensives Thema

Da bei den Pseudoprimzahlen, insbesondere denen, die unter das Schema fermatsche Pseudoprimzahlen fallen, oft große Potenzen auftauchen, kommt man, wenn man das in diesem Buch geschriebene nachvollziehen möchte, nicht darum herum, selbst Programme zu schreiben. Manches läßt sich auch "zu Fuß" oder mit dem Taschenrechner nachrechnen, aber ohne Computer kommt man letztlich nicht aus. In dem Buch ist auch ein Kapitel mit fertigen Quellcodes, aber man läßt sich möglicherweise etwas entgehen, wenn man sich nicht selbst Gedanken macht, und die Programme selbst schreibt. Aber das muss der Leser letztendlich selber wissen.

Unterscheidung

Wenn in dem Text über eine Zahl gesagt wird, sie sei eine Pseudoprimzahl, dann bedeutet das, dass diese Zahl zusammengesetzt ist, und sich nach irgendeinem Kriterium wie eine Primzahl verhält. Genauso bedeutet ein eine Zahl ist eine starke Pseudoprimzahl, dass eine Basis existiert, zu der sich diese zusammengesetzte Zahl, aufgrund des Kriteriums für starke Pseudoprimzahlen, wie eine Primzahl verhält.

Ist dagegen von einer fpsp(a) die Rede, also einer fermatschen Pseudoprimzahl zu einer bestimmten Basis $a$ , dann ist klar, dass man sich genau auf diese Basis $a\$ bezieht (abgesehen davon, dass diese fermatsche Pseudoprimzahl noch zu anderen Basen pseudoprim ist).

Pseudoprimzahlen

Definition

Eine Pseudoprimzahl ist eine zusammengesetzte natürliche Zahl, die bestimmte Eigenschaften mit Primzahlen gemeinsam hat. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da es viele solche Eigenschaften gibt, ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll.

Hintergrund

Die Beschäftigung mit Pseudoprimzahlen ist aus dem Bedürfnis entstanden, schnelle Primzahltests für große Zahlen zu finden.

Primzahlen sind natürliche Zahlen größer 1, die nur durch 1 und durch sich selbst teilbar sind. So sind sie definiert.

Allerdings lassen sich damit größere Zahlen schlecht darauf prüfen, ob sie Primzahlen sind. Wie unpraktisch diese Eigenschaft für den Primzahlentest ist, lässt sich daran ermessen, dass um eine Zahl der Größenordnung $\approx 10^{100}$ auf ihre Primalität zu testen, ihre Teilbarkeit durch $\approx 10^{50}$ Zahlen getestet werden müsste.

Aber Primzahlen haben noch viele andere Eigenschaften, Eigenschaften der Form: "Wenn $p\$ eine Primzahl ist, dann hat $p\$ die Eigenschaft $x$ ".

Um aus dem Buch Prime Numbers - A Computational Perspective 1 zu zitieren: "Wenn $p\$ eine Primzahl ist, dann ist $p\$ gleich 2, oder $p\$ ist eine ungerade Zahl". In dieser Richtung funktioniert die Aussage. Allerdings lässt sie sich nicht umkehren: "Wenn $p\$ gleich 2 oder eine ungerade Zahl ist, dann ist $p\$ eine Primzahl" ist ausgemachter Blödsinn. Es gibt weitere solcher "Wenn $p\$ eine Primzahl ist, dann hat $p\$ die Eigenschaft $x$ ", die sinnvoller sind, deren Umkehrung aber ebenfalls falsche Schlüsse wären:

Wenn

\ p\

eine Primzahl und größer als 3 ist,

dann hat $\ p\$ die Form $4n+1\$ oder $4n-1\$ (das gilt für alle ungeraden Zahlen)
dann hat $\ p\$ die Form $6n+1\$ oder $6n-1\$ (ungerade und nicht durch 3 teilbar)
dann teilt $\ p\$ jede Zahl der Form $\ a^{p}-a\$ mit $a\geq 2$
dann teilt $\ p\$ den Ausdruck $L_{p}-1$ , wobei $\ L_{p}\$ das p.te Glied der Lucas-Folge ist.
dann teilt $\ p\$ das p.te Glied der Perrin-Folge

Vermeintliche Primzahlen, die man aus der Umkehrung solcher "Wenn $p\$ eine Primzahl ist, dann hat $p\$ die Eigenschaft $x$ "-Regeln bekommt, nennt man Pseudoprimzahlen. Das allerdings mit einer gewissen Einschränkung:

Zusammengesetze Zahlen werden nicht als Pseudoprimzahlen bezeichnet, nur weil sie den Formen

4n+1\

,

4n-1\

,

6n+1\

bzw.

6n-1\

entsprechen. Dazu sind schon striktere Eigenschaften wie beispielsweise

q\

teilt

a^{q}-a

oder

q\

teilt

P_{q}\

oder

q\

teilt

L_{q}-1\

nötig.

Zusammengesetze Zahlen, die dem Satz $a^{p}\equiv a{\pmod {p}}$ (kleiner fermatscher Satz) genügen, nennt man fermatsche Pseudoprimzahlen zur Basis $a$ . Dies ist die bekannteste und wichtigste Klasse der Pseudoprimzahlen.

Allgemein sind Pseudoprimzahlen zusammengesetze Zahlen, die einen probabilistischen Primzahltest bestehen.

Der Umkehrschluss

Wenn eine natürliche Zahl eine Eigenschaft, die alle Primzahlen haben, nicht hat, kann sie keine Primzahl sein; dieser Schluss ist immer zulässig. Wenn die Zahl eine solche Eigenschaft hat, und die Eigenschaft selten bei zusammengesetzten Zahlen auftritt, kann daraus nur geschlossen werden, dass sie wahrscheinlich eine Primzahl ist.

Unterscheidung

Wenn im Text über eine Zahl gesagt wird, sie sei eine Pseudoprimzahl, dann bedeutet das, dass diese Zahl zusammengesetzt ist, und sich nach irgendeinem Kriterium wie eine Primzahl verhält. Genauso bedeutet ein eine Zahl ist eine starke Pseudoprimzahl, dass eine Basis existiert, zu der sich diese zusammengesetzte Zahl, aufgrund des Kriteriums für starke Pseudoprimzahlen, wie eine Primzahl verhält.

Ist dagegen von einer fpsp(a) die Rede, also einer fermatschen Pseudoprimzahl zu einer bestimmten Basis $a$ , dann ist klar, dass man sich genau auf diese Basis $a\$ bezieht (abgesehen davon, dass diese fermatsche Pseudoprimzahl noch zu anderen Basen pseudoprim ist).

Absolute Pseudoprimzahlen

Absolute Pseudoprimzahlen bezüglich einer Eigenschaft sind zusammengesetze Zahlen, die mit allen Parametern, die bestimmte Bedingungen erfüllen, pseudoprim bezüglich dieser Eigenschaft sind; Bedingungen für Parameter sind zum Beispiel, dass bei Fermatschen Pseudoprimzahlen die Basis teilerfremd zu $n$ ist, oder bei Lucas-Pseudoprimzahlen die Diskriminante $D=P^{2}-4Q$ den gleichen Wert hat.

Starke Pseudoprimzahlen

Starke Pseudoprimzahlen bezüglich einer Kongruenzbedingung sind zusammengesetzte Zahlen, die eine verschärfte Form derselben Kongruenzbedingung mit denselben Parametern erfüllen, z. B. statt $a^{n-1}\equiv 1{\pmod {n}}$ :

$a^{d}\equiv 1{\pmod {n}}$ oder
$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}$ für ein $0<=r<s$ , jeweils mit $n-1=d\cdot 2^{s}$ .

Aus der Erfüllung der starken Kongruenzbedingung folgt die Erfüllung der ursprünglichen. Der Parameter $a$ bleibt dabei gleich.

Ein paar Daten zu den fermatschen Pseudoprimzahlen

Zu jeder Basis $a\geq 2$ gibt es eine kleinste fermatsche Pseudoprimzahl. In der folgenden Tabelle sind die kleinsten Pseudoprimzahlen bis zur Basis 121 aufgeführt:

Die kleinste fermatsche Pseudoprimzahl zur Basis a
a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp
2:	341	22:	69	42:	205	62:	91	82:	91	102:	133
3:	91	23:	33	43:	77	63:	341	83:	105	103:	133
4:	15	24:	115	44:	65	64:	85	84:	415	104:	145
5:	124	25:	28	45:	76	65:	112	85:	129	105:	451
6:	35	26:	45	46:	133	66:	91	86:	145	106:	133
7:	25	27:	65	47:	65	67:	85	87:	91	107:	133
8:	21	28:	45	48:	91	68:	91	88:	91	108:	341
9:	28	29:	35	49:	66	69:	85	89:	99	109:	117
10:	33	30:	49	50:	119	70:	169	90:	623	110:	259
11:	15	31:	49	51:	65	71:	105	91:	115	111:	190
12:	65	32:	93	52:	85	72:	65	92:	105	112:	121
13:	21	33:	85	53:	65	73:	111	93:	301	113:	133
14:	39	34:	55	54:	265	74:	91	94:	121	114:	205
15:	341	35:	51	55:	63	75:	91	95:	141	115:	133
16:	51	36:	91	56:	95	76:	105	96:	133	116:	195
17:	45	37:	45	57:	65	77:	247	97:	105	117:	145
18:	25	38:	65	58:	133	78:	341	98:	153	118:	121
19:	45	39:	95	59:	87	79:	91	99:	145	119:	177
20:	57	40:	91	60:	341	80:	169	100:	153	120:	187
21:	55	41:	105	61:	91	81:	85	101:	175	121:	133

Wenn man nun alle Pseudoprimzahlen aus der Tabelle, unter der Weglassung der doppelten Pseudoprimzahlen auflistet, bekommt man folgende Folge:

 15,  21,  25,  28,  33,  35,  39,  45,  49,  51,  55,  57,  63,  65,  66,  69,  76,  77,  85,  87,  91,  93,  95,  99,
105, 111, 112, 115, 117, 119, 121, 124, 129, 133, 141, 145, 153, 169, 175, 177, 187, 190, 195, 205, 247, 259, 265, 301,
341, 415, 451, 623

Das sind 52 Zahlen. Zum Vergleich: Bis 10 existieren 4 Primzahlen, hier sind es 0 Pseudoprimzahlen; bis 100 sind es 25 Primzahlen, hier sind es 24 Pseudoprimzahlen; bis 1000 sind es 168 Primzahlen, hier sind es 52. Allerdings muß man zugestehen, das noch gar nicht alle Pseudoprimzahlen berücksichtigt werden konnten. Wie aber verhält sich die Verteilung der Pseudoprimzahlen nun wirklich? Gibt es innerhab bestimmter Grenzen mehr Pseudoprimzahlen als Primzahlen, oder verhält es sich umgekehrt?

Dabei muß man Unterscheiden. Meint man die fermatschen Pseudoprimzahlen zu einer bestimmten Basis $a\$ , so sind es, in definierten Grenzen, weniger Pseudoprimzahlen als Primzahlen:

Basis	Fermatsche Pseudoprimzahlen
2	341, 561, 645, 949, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, ...
3	91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, ...
4	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, ...
5	124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5611, 5662, 5731, 7449, 7813, 8029, ...
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, ...
7	25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, ...
8	21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, ...
9	28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, ...
10	33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, ...

Meint man dagegen die Menge aller fermatschen Pseudoprimzahlen, die zu irgendeiner Basis $a\geq 2$ pseudoprim ist, dann gibt es, in definierten Grenzen mehr Pseudoprimzahlen als Primzahlen:

  15    21    25    28    33    35    39    49    51    52    55    57    63    65    66    69    70    75
  76    77    85    87    91    93    95    99   105   111   112   115   117   119   121   123   124   125
 129   130   133   135   141   143   145   147   148   153   154   155   159   161   165   169   171   172
 175   176   177   183   185   186   187   189   190   195   196   201   203   205   207   208   209   213
 215   217   219   221   225   231   232   235   237   238   244   245   246   247   249   253   255   259
 261   265   267   268   273   275   276   279   280   285   286   287   289   291   292   295   297   299
 301   303   304   305   309   310   315   316   319   321   322   323   325   327   329   333   335   339
 341

Pseudoprimzahlen

Der kleine fermatsche Satz besagt, dass $\ a^{p}-a\$ für jede Primzahl $\ p\$ und jede natürliche Zahl $a\geq 2\$ durch $\ p\$ teilbar ist.

Für jede Primzahl $\ p\$ gilt also

\ a^{p}\equiv a{\pmod {p}}\

mit

a>1

und

\ a^{p-1}\equiv 1{\pmod {p}}

, wenn

a

kein Vielfaches von

p

ist.

(1)

Definition

Eine zusammengesetzte Zahl $q\$ ist fermatsche Pseudoprimzahl zur Basis $a$ , wenn mit $\operatorname {ggT} (a,q)=1$ und $2\leq a\leq q-2\$ für $a\$ und $q\$ gilt:

a^{q-1}\equiv 1{\pmod {q}}

.

Beispiel:

15=3\cdot 5

ist eine zusammengesetze Zahl

$4^{15-1}\$	$\equiv 1{\pmod {15}}$
$11^{15-1}\$	$\equiv 1{\pmod {15}}$

Anzahl der Basen

Wenn die Primteiler $\ p_{i}\$ einer Pseudoprimzahl $n$ bekannt sind, kann die Anzahl der Basen, zu denen sie pseudoprim ist, berechnet werden:

Mit der Faktorisierung

n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}

ist die Anzahl der Basen $<n$ einschließlich 1 und bei ungeraden Zahlen n-1

\prod _{i=1}^{k}\gcd(n-1,p_{i}-1)

.^[1]

Eigenschaften

Abgesehen von den Dreierpotenzen, also 9, 27, 81, 243, 729, ..., sind alle ungeraden zusammengesetzten Zahlen fermatsche Pseudoprimzahlen zu irgendeiner Basis. Bei den geraden zusammengesetzen Zahlen sieht das noch ein wenig anders als. Dort gibt es mehr zusammengesetzte Zahlen, die keine Fermatschen Pseudoprimzahlen sind.

Zusammenhänge zwischen den Basen

Natürlich gibt es zu einer fermatschen Pseudoprimzahl $q\$ niemals nur eine Basis $a\$ , zu der sie pseudoprim ist.

Das lässt sich an einer Pseudoprimzahl, sagen wir beispielsweise mal 21, zeigen:

Die 21 ist pseudoprim zur Basis 8.

Wenn eine ungerade Zahl $\ q\$ zu einer Basis $\ a\$ mit $\ a<q\$ pseudoprim ist, so ist sie auch zur Basis $\ (q-a)\$ pseudoprim.

Da 21 pseudoprim zur 8 ist, ist 21 auch pseudoprim zu (21 - 8) = 13.

Wenn eine Zahl $\ q\$ zu einer Basis $\ a\$ mit $\ a<q\$ pseudoprim ist, so ist sie auch zu jeder Basis $\ a^{n}\$ mit ganzzahligem Exponenten $\ n>1\$ pseudoprim.

Da 21 pseudoprim zu 8 und 13 ist, ist 21 auch zu

8^{2}=64,\ 13^{2}=169,\ 8^{3}=512,\ 13^{3}=2197,\ ...\

pseudoprim.

Wenn eine Zahl $\ q\$ zu einer Basis der Form $\ a^{n}\$ mit $\ n\geq 1\$ pseudoprim ist, so ist sie auch pseudoprim zu $\ a^{n}\operatorname {mod} \ q\$ mit $\ n\geq 1\$
Wenn eine Zahl $\ q\$ zu den Basen $\ a\$ und $\ b\$ pseudoprim ist, so ist sie auch pseudoprim zu $\ a\cdot b\$ : $a^{q-1}\equiv b^{q-1}\equiv 1{\pmod {q}}\quad \Rightarrow \quad a^{q-1}\cdot b^{q-1}=(a\cdot b)^{q-1}\equiv 1{\pmod {q}}$ .

Umgekehrt gilt das nicht: zum Beispiel ist 341 pseudoprim zur Basis 15, aber nicht zu 3 oder 5.

Teiler

Für alle Primteiler $p$ einer Fermatschen Pseudoprimzahl $n\$ gilt

$n\equiv 1{\pmod {l_{a}(p)}}$ und damit
$n\equiv p{\pmod {p\cdot l_{a}(p)}}$ ,

wobei $l_{a}(p)$ die multiplikative Ordnung von $p$ zur Basis $a$ ist.^[2]

Fermatsche Pseudoprimzahlen

Eulersche Pseudoprimzahlen

Starke Pseudoprimzahlen

Ein paar Daten zu den fermatschen Pseudoprimzahlen

Zu jeder Basis $a\geq 2$ gibt es eine kleinste fermatsche Pseudoprimzahl. In der folgenden Tabelle sind die kleinsten Pseudoprimzahlen bis zur Basis 121 aufgeführt:

Die kleinste fermatsche Pseudoprimzahl zur Basis a
a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp	a	fpsp
2:	341	22:	69	42:	205	62:	91	82:	91	102:	133
3:	91	23:	33	43:	77	63:	341	83:	105	103:	133
4:	15	24:	115	44:	65	64:	85	84:	415	104:	145
5:	124	25:	28	45:	76	65:	112	85:	129	105:	451
6:	35	26:	45	46:	133	66:	91	86:	145	106:	133
7:	25	27:	65	47:	65	67:	85	87:	91	107:	133
8:	21	28:	45	48:	91	68:	91	88:	91	108:	341
9:	28	29:	35	49:	66	69:	85	89:	99	109:	117
10:	33	30:	49	50:	119	70:	169	90:	623	110:	259
11:	15	31:	49	51:	65	71:	105	91:	115	111:	190
12:	65	32:	93	52:	85	72:	65	92:	105	112:	121
13:	21	33:	85	53:	65	73:	111	93:	301	113:	133
14:	39	34:	55	54:	265	74:	91	94:	121	114:	205
15:	341	35:	51	55:	63	75:	91	95:	141	115:	133
16:	51	36:	91	56:	95	76:	105	96:	133	116:	195
17:	45	37:	45	57:	65	77:	247	97:	105	117:	145
18:	25	38:	65	58:	133	78:	341	98:	153	118:	121
19:	45	39:	95	59:	87	79:	91	99:	145	119:	177
20:	57	40:	91	60:	341	80:	169	100:	153	120:	187
21:	55	41:	105	61:	91	81:	85	101:	175	121:	133

Wenn man nun alle Pseudoprimzahlen aus der Tabelle, unter der Weglassung der doppelten Pseudoprimzahlen auflistet, bekommt man folgende Folge:

 15,  21,  25,  28,  33,  35,  39,  45,  49,  51,  55,  57,  63,  65,  66,  69,  76,  77,  85,  87,  91,  93,  95,  99,
105, 111, 112, 115, 117, 119, 121, 124, 129, 133, 141, 145, 153, 169, 175, 177, 187, 190, 195, 205, 247, 259, 265, 301,
341, 415, 451, 623

Das sind 52 Zahlen. Zum Vergleich: Bis 10 existieren 4 Primzahlen, hier sind es 0 Pseudoprimzahlen; bis 100 sind es 25 Primzahlen, hier sind es 24 Pseudoprimzahlen; bis 1000 sind es 168 Primzahlen, hier sind es 52. Allerdings muß man zugestehen, das noch gar nicht alle Pseudoprimzahlen berücksichtigt werden konnten. Wie aber verhält sich die Verteilung der Pseudoprimzahlen nun wirklich? Gibt es innerhab bestimmter Grenzen mehr Pseudoprimzahlen als Primzahlen, oder verhält es sich umgekehrt?

Dabei muß man Unterscheiden. Meint man die fermatschen Pseudoprimzahlen zu einer bestimmten Basis $a\$ , so sind es, in definierten Grenzen, weniger Pseudoprimzahlen als Primzahlen:

Basis	Fermatsche Pseudoprimzahlen
2	341, 561, 645, 949, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, ...
3	91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, ...
4	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, ...
5	124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5611, 5662, 5731, 7449, 7813, 8029, ...
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, ...
7	25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, ...
8	21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, ...
9	28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, ...
10	33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, ...

Meint man dagegen die Menge aller fermatschen Pseudoprimzahlen, die zu irgendeiner Basis $a\geq 2$ pseudoprim ist, dann gibt es, in definierten Grenzen mehr Pseudoprimzahlen als Primzahlen:

  15    21    25    28    33    35    39    49    51    52    55    57    63    65    66    69    70    75
  76    77    85    87    91    93    95    99   105   111   112   115   117   119   121   123   124   125
 129   130   133   135   141   143   145   147   148   153   154   155   159   161   165   169   171   172
 175   176   177   183   185   186   187   189   190   195   196   201   203   205   207   208   209   213
 215   217   219   221   225   231   232   235   237   238   244   245   246   247   249   253   255   259
 261   265   267   268   273   275   276   279   280   285   286   287   289   291   292   295   297   299
 301   303   304   305   309   310   315   316   319   321   322   323   325   327   329   333   335   339
 341

Pseudoprimzahlen

Quellen

Pseudoprimzahlen

Für jede ungerade Primzahl $p$ gilt mit jeder teilerfremden Basis $a$ die Kongruenz

a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right)=\pm 1{\pmod {n}}

.

Dabei bezeichnet $\left({\frac {a}{n}}\right)$ das Jacobi-Symbol.

Eulersche Pseudoprimzahl

Eine zusammengesetzte Zahl n ist eine eulersche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl $a$ im Bereich $1<a<n-1$ als Basis gibt, mit der entweder

a^{\frac {n-1}{2}}\equiv 1{\pmod {n}}

(1a)

oder

a^{\frac {n-1}{2}}\equiv -1{\pmod {n}}

(1b)

ist.

Eine solche Zahl nennt man eulersche Pseudoprimzahl zur Basis a, kurz: EPsP(a).

Eulersche Pseudoprimzahlen sind auch Fermatsche Pseudoprimzahlen

Es lässt sich ziemlich einfach, nämlich durch Quadrieren, zeigen, dass jede eulersche Pseudoprimzahl auch eine fermatsche Pseudoprimzahl ist. Es sei n eine eulersche Pseudoprimzahl zur Basis a. Es gilt also:

a^{\frac {n-1}{2}}\equiv \pm 1{\pmod {n}}.

Folglich ist:

a^{n-1}=\left(a^{\frac {n-1}{2}}\right)^{2}\equiv (\pm 1)^{2}=1{\pmod {n}},

und deshalb ist n auch eine fermatsche Pseudoprimzahl zur Basis a.

Daraus dass eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl ist, lässt sich nicht der Umkehrschluss ziehen, dass jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das lässt sich anhand der fermatschen Pseudoprimzahl 15 zeigen:

11^{7}\equiv 11{\pmod {15}}

.

Die Zahl 15 ist also keine eulersche Pseudoprimzahl zur Basis 11. Aber

11^{14}\equiv 1{\pmod {15}},

demzufolge ist 15 eine fermatsche Pseudoprimzahl zur Basis 11.

Euler-Jacobi-Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl $n$ heißt Euler-Jacobi-Pseudoprimzahl zur Basis a, wenn $n$ und $a$ teilerfremd sind und

a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

(2)

ist.

Euler-Jacobi-Pseudoprimzahlen werden oft auch "Eulersche Pseudoprimzahlen" genannt.

Da der Wert des Jacobi-Symbols mit teilerfremden Parametern nur 1 oder -1 sein kann, ist jede Euler-Jacobi-Pseudoprimzahl auch eine eulersche Pseudoprimzahl;

für 1 gilt Kongruenz 1a,
für -1 gilt 1b.

Anzahl der Basen

Wenn die Primteiler $\ p_{i}\$ einer zusammengesetzten Zahl $n$ bekannt sind, kann die Anzahl der Basen, zu denen sie Euler-Jacobi-Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}{\text{ und }}\ n-1=d\cdot 2^{s}{\text{ mit }}d{\text{ ungerade }}

ist die Anzahl der Basen $<n$ einschließlich 1 und n-1

\prod _{i=1}^{k}\gcd \left({\frac {n-1}{2}},\ p_{i}^{'}\right)\cdot {\begin{cases}2&{\text{wenn }}\nu =s\\1/2&{\text{wenn }}\exists \ p_{i}{\text{ mit }}\nu _{2}(p_{i})<s{\text{ und }}\alpha _{i}{\text{ ungerade}}\\1&{\text{sonst }}\end{cases}}

^[1]

Dabei ist

$\ s$ der größte Exponent, mit dem $\ 2^{s}|n-1\$ gilt,, so dass $\ n-1=d\cdot 2^{s}\$ ist,
$\ p_{i}^{'}$ der größte ungerade Teiler von $\ p_{i}-1$ ,
$\ \nu _{2}(p_{i})$ der größte Exponent, mit dem $\ 2^{\nu _{2}(p_{i})}|p_{i}-1\$ gilt, so dass $\ p_{i}-1=2^{\nu _{2}(p_{i})}\cdot p_{i}^{'}\$ ist und
$\ \nu$ das Minimum aller $\nu _{2}(p_{i})$ .

Quellen

↑ On the number of false witnesses for a composite number, S. 270 (5.4)

Fermatsche Pseudoprimzahlen

Pseudoprimzahlen

Starke Pseudoprimzahlen

Pseudoprimzahlen

Jede ungerade Primzahl $n$ erfüllt mit jeder teilerfremden ganzzahligen Basis $a$ eine der Kongruenzen

a^{d}\equiv 1{\pmod {n}}\quad

mit

\ n-1=d\cdot 2^{s}\

und

d\

ungerade

(1)

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad

für ein

r

mit

0\leqq r<s

(2)

. Anmerkung: Kongruenz (2) ist gleichbedeutend mit $a^{d\cdot 2^{r}}\equiv n-1{\pmod {n}}$ .

Definition

Eine ungerade Zahl $n$ ist starke Pseudoprimzahl zur Basis $a$ , wenn sie zusammengesetzt ist, und mit einer ganzzahligen Basis $a$ , für die $1<a<n-1{\pmod {n}}$ gilt, eine der obengenannten Kongruenzen erfüllt ist. In dieser Hinsicht verhält sie sich wie eine Primzahl.

Die obengenannten Kongruenzen werden im Miller-Rabin-Test^[1] genutzt, um zu prüfen ob eine ungerade Zahl (wahrscheinlich) eine Primzahl oder sicher keine ist; dabei kann durch Tests mit mehreren Basen die Wahrscheinlichkeit, dass eine Pseudoprimzahl den Test besteht, reduziert werden.

Eigenschaften

Im Gegensatz zu den Fermatschen Pseudoprimzahlen gibt es keine starken Pseudoprimzahlen, die zu jeder teilerfremden Basis pseudoprim sind; eine Entsprechung zu den Carmichael-Zahlen gibt es also nicht.

Alle zusammengesetzten Mersennezahlen ( $2^{p}-1$ mit $\ p$ = prim) sind starke Pseudoprimzahlen zur Basis 2.

Alle zusammengesetzten Fermatzahlen ( $2^{2^{n}}+1$ ) sind starke Pseudoprimzahlen zur Basis 2.^[2]

$(4^{p}+1)/5$ ist starke Pseudoprimzahl zur Basis 2, wenn $p>5$ und eine Primzahl ist.^[3]

Die Quadrate der Wieferich-Primzahlen sind starke Pseudoprimzahlen zur Basis 2.

Bezug zu Eulerschen Pseudoprimzahlen

Jede starke Pseudoprimzahl $n\$ zur Basis $a\$ ist auch eine Eulersche Pseudoprimzahl zur Basis $a\$ .
Warum? Für eine eulersche Pseudoprimzahl zur Basis $a\$ gilt $a^{\frac {n-1}{2}}\equiv \pm 1{\pmod {n}}$ .

$a^{\frac {n-1}{2}}$ lässt sich auch als $a^{d\cdot 2^{s-1}}$ schreiben. Wenn nun $a^{d}\equiv \pm 1{\pmod {n}}$ gilt, gilt auch $(a^{d})^{2^{s-1}}\equiv \pm 1{\pmod {n}}$ und damit auch $a^{\frac {n-1}{2}}=a^{d\cdot 2^{s-1}}\equiv \pm 1{\pmod {n}}$ .

Jede eulersche Pseudoprimzahl der Form $\ n=4\cdot k+3\$ ist starke Pseudoprimzahl:
in diesem Fall ist $\ d={\frac {n-1}{2}}$ und $\ s=1\$ und damit $\ a^{d}=a^{\frac {n-1}{2}}=a^{d\cdot 2^{r}}$ ; mit $\ a^{\frac {n-1}{2}}\equiv \pm 1{\pmod {n}}\$ ist also eine der obengenannten Kongruenzen erfüllt.

Teiler

Für alle Primteiler $p$ einer starken Pseudoprimzahl $n\$ gilt

$n\equiv 1{\pmod {l_{a}(p)}}$ und damit
$n\equiv p{\pmod {p\cdot l_{a}(p)}}$ ,

wobei $l_{a}(p)$ die multiplikative Ordnung von $p$ zur Basis $a$ ist.^[4] ^[5]^[6]

Die höchste Zweierpotenz, durch die die multiplikative Ordnung eines Primteilers teilbar ist, ist für alle Teiler einer starken Pseudoprimzahl gleich, d. h. alle multiplikativen Ordnungen der Primteiler derselben starken Pseudoprimzahl sind Produkt einer ungeraden Zahl und derselben Zweierpotenz (einschließlich $2^{0}$ ).^[7]

Starke Pseudoprimzahlen sind weitgehend quadratfrei; nur die Quadrate der Wieferich-Primzahlen zur Basis $a$ sind starke Pseudoprimzahlen zur Basis $a$ und können Teiler einer solchen sein. Mit der Basis 2 sind das die Wieferich-Primzahlen 1093 und 3511 (weitere sind bisher nicht bekannt).

Starke Pseudoprimzahlen lassen sich häufig als Produkte der Form

\ q=(2\cdot k\cdot x+1)\cdot (2\cdot m\cdot x+1)\

mit

\quad x\in \mathbb {N}

,

\quad \gcd(k,m)=1\

und

\quad 0<k\ll q,\ 0<m\ll q\

ausdrücken. Umgekehrt ist der Anteil starker Pseudoprimzahlen bei solchen Produkten deutlich höher als bei ungeraden Zahlen allgemein.

Anzahl der Basen

Wenn die Primteiler $\ p_{i}\$ einer zusammengesetzten Zahl $n$ bekannt sind, kann die Anzahl der Basen, zu denen sie starke Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}

ist die Anzahl der Basen $<n$ einschließlich 1 und n-1

\left(1+{\frac {2^{k\nu }-1}{2^{k}-1}}\right)\prod _{i=1}^{k}\gcd \left(d,\ p_{i}^{'}\right)

^[8]

Dabei ist

$\ d$ der größte ungerade Teiler von $\ n-1$ (wie oben)
$\ p_{i}^{'}$ der größte ungerade Teiler von $\ p_{i}-1$ ,
$\ \nu _{2}(p_{i})$ der größte Exponent, mit dem $\ 2^{\nu _{2}(p_{i})}|p_{i}-1\$ gilt, so dass $\ p_{i}-1=2^{\nu _{2}(p_{i})}\cdot p_{i}^{'}\$ ist und
$\ \nu$ das Minimum aller $\nu _{2}(p_{i})$ .

Basen, zu denen eine zusammengesetze Zahl $n\$ keine Pseudoprimzahl ist, werden Zeugen für die Zusammengesetztheit der Zahl genannt; solche zu denen sie pseudoprim ist, werden „falsche Zeugen“ genannt. Maximal ein Viertel der teilerfremden Basen zwischen 0 und n sind falsche Zeugen.

Häufigkeit

Starke Pseudoprimzahlen zu einer festen Basis sind viel seltener als Primzahlen. Folgende Tabelle zeigt die Anzahl starker Pseudoprimzahlen zur Basis 2 im Vergleich zur Anzahl fermatscher Pseudoprimzahlen zur Basis 2 und der Primzahlen bis zur angegebenen Obergrenze.

Anzahl Starker Pseudoprimzahlen zur Basis 2 im Vergleich zu Primzahlen
Obergrenze	Primzahlen^[9]	Fermatsche Pseudoprimzahlen	Starke Pseudoprimzahlen^[10]
$10^{9}\$	50.847.534	5.597	1.282
$10^{12}$	37.607.912.018	101.629	22.407
$10^{15}$	29.844.570.422.669	1.801.533	419.489
$10^{18}$	24.739.954.287.740.860	33.763.684	8.646.507

Restklassen

Starke Pseudoprimzahlen liegen wesentlich häufiger in der Restklasse 1 modulo kleiner Zahlen $(m)$ als in anderen Restklassen. Folgende Tabelle zeigt die Verteilung der starken Pseudoprimzahlen zur Basis 2 bis 10¹⁵ auf Restklassen modulo m an ein paar Beispielen.

	Anzahl starker Pseudoprimzahlen zur Basis 2 in Restklasse
m	0	1	2	3	4	5	6	7
3	26	327193	92270
5	1373	199879	84716	74590	58931
7	370	142844	49224	62834	47482	57853	58882
8	0	207103	0	44885	0	122473	0	45028

Beispiele

Um zu zeigen, wie unterschiedlich starke Pseudoprimzahlen ausfallen können, werden als Beispiele die drei Zahlen 781, 1541 und 25 gezeigt. An der Zahl 781 wird erstmal die Zerlegung gezeigt:

Zerlegung

Gesucht wird das $d\$ zu einer Zahl $n\$ so dass $n=d\cdot 2^{s}+1\$ mit ungeradem $d\$ gilt. Die Formel können wir umstellen:

$n=d\cdot 2^{s}+1$
$n-1=d\cdot 2^{s}$
${\frac {n-1}{2^{s}}}=d$

Am Beispiel der Zahl 781 sieht das so aus: Die Primfaktorzerlegung von $781-1=2^{2}\cdot 3\cdot 5\cdot 13\$ . Wenn man die 2er-Potenzen entfernt, bleibt für $n=781\$ das $d=3\cdot 5\cdot 13=195\$ übrig.

781 zur Basis 5

$n=781\ \ \ d=195\$

$5^{195}\equiv 1{\pmod {781}}$ also ist 781 eine starke Pseudoprimzahl zur Basis 5.

1541 zur Basis 5

$n=1541\ \ \ d=385\$

$5^{385}\equiv 1540{\pmod {1541}}$ also ist 1541 eine starke Pseudoprimzahl zur Basis 5.

25 zur Basis 7

$n=25\ \ \ d=3\$

$7^{3}\equiv 18{\pmod {25}}$

$7^{6}\equiv 24{\pmod {25}}$ also ist 25 eine starke Pseudoprimzahl zur Basis 7.

305 zur Basis 11

Dies ist ein Gegenbeispiel.

$n=305\ \ \ d=19\$

$11^{19}\equiv 111{\pmod {305}}$

$11^{38}\equiv 121{\pmod {305}}$

$11^{76}\equiv 1{\pmod {305}}$

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11.

Quellen

↑ Miller-Rabin-Test
↑ Pseudoprimes and Fermat numbers
↑ Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7 http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf
↑ The pseudoprimes to 25 * 10^9
↑ Glossar
↑ Multiplicative order
↑ New Implementations for Tabulating Pseudoprimes and Liars.pdf
↑ On the number of false witnesses for a composite number, S. 270 (5.4)
↑ Primzahlsatz
↑ Pseudoprime Statistics, Tables

Fermatsche Pseudoprimzahlen

Eulersche Pseudoprimzahlen

Starke Pseudoprimzahlen

Pseudoprimzahlen

Carmichael-Zahlen

Die Carmichael-Zahl ist eine besondere Form der fermatschen Pseudoprimzahl. In ihren Eigenschaften kommt sie der Primzahl am nächsten. Sowohl für Primzahlen als auch für Carmichael-Zahlen gilt der kleine Fermatsche Satz: Für jede ganze Zahl $a\$ gilt $n|a^{n}-a$ . Erst wenn man diesen Satz modifiziert, ergibt sich ein Unterschied zwischen Primzahl und Carmichael-Zahl.

Carmichael-Zahlen haben folgende Eigenschaften:

Eine Carmichael-Zahl ist quadratfrei.
Eine Carmichael-Zahl hat mindestens drei Primfaktoren.
Für jeden Primfaktor $p_{i}$ einer Carmichael-Zahl $c=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$ gilt $\ p_{i}-1\$ teilt $\ c-1$ .
Für alle Basen $a$ , die zu einer Carmichael-Zahl $c\$ teilerfremd sind, ist $a^{c-1}\equiv 1{\pmod {c}}$ .

Quadratfreiheit

Warum muss eine Carmichael-Zahl quadratfrei sein? Angenommen es gibt eine Carmichael-Zahl, die nicht quadratfrei ist. Sie hat der Einfachheit halber die Form $c=p_{1}^{n}\cdot p_{2}$ mit $n\geq 2$ . Außerdem sind $p_{1}\$ und $p_{2}\$ Primzahlen. Es gilt also $p_{1}\$ teilt $c$ . Mit der Kenntnis der Faktorisierung von $c\$ kann man die Carmichael-Funktion $\lambda (c)$ berechnen:

\lambda (c)=\lambda (p_{1}^{n}\cdot p_{2})=\operatorname {kgV} \{\lambda (p_{1}^{n}),\lambda (p_{2})\}=\operatorname {kgV} \{(p_{1}-1)(p_{1}^{n-1}),p_{2}-1\}

Da $c-1\$ durch $\lambda (c)\$ teilbar ist, ist $c-1\$ auch durch $(p_{1}-1)(p_{1}^{n-1})\$ teilbar, und damit gilt dadurch auch dass $c-1\$ durch $p_{1}\$ teilbar ist. Und das führt zu einem Widerspruch.

Es gilt nämlich $p_{1}\$ teilt $c\$ und $p_{1}\$ teilt $c-1$ . Der Widerspruch liegt darin, dass $c\$ und $c-1\$ zueinander teilerfremd sind, also keinen gemeinsamen Teiler besitzen. Also ist es nicht möglich, dass eine Carmichael-Zahl nicht quadratfrei ist.

mindestens drei Primfaktoren

Jede Carmichael-Zahl besitzt mindestens 3 voneinander verschiedene Primfaktoren.

Beweis: Durch Widerspruch.

Sei $n\$ eine Carmichael-Zahl. Angenommen, $n=p\cdot q$ , wobei $p\$ und $q\$ Primfaktoren seien. Zunächst muss wegen der oben gezeigten Quadratfreiheit gelten, dass $p\neq q$ . Wir können also annehmen, dass $p<q\$ (man kann die Schlüsse analog mit $p>q\$ ziehen). Nun gilt wegen Eigenschaft (3) $q-1|n-1\$ also $q-1|p\cdot q-1$ .

Damit ist ${\frac {p\cdot q-1}{q-1}}=p+{\frac {p-1}{q-1}}\in \mathbb {Z}$ . Das bedeutet aber, $(q-1)|(p-1)\$ im Widerspruch zu $p<q$ . Also war die Annahme falsch. Carmichael-Zahlen mit nur einem Primfaktor kann es nach Definition nicht geben (denn sie sind keine Primzahlen), und dass es Carmichael-Zahlen mit 3 Primfaktoren gibt, zeigt bereits die allererste: $561=17\cdot 11\cdot 3$ . Zusammen genommen ist also gezeigt worden, dass eine Carmichael-Zahl mindestens 3 Primfaktoren hat.

Satz von Korselt

Der deutsche Mathematiker Alwin Reinhold Korselt hat 1899 ein Theorem über eine bestimmte Art von Pseudoprimzahlen, die später Carmichael-Zahlen genannt wurden, aufgestellt:

Es existieren ungerade, quadratfreie natürliche Zahlen $c$ , so dass $a^{c}-a$ für alle natürlichen Zahlen $a$ ein Vielfaches von $c$ ist
Für alle Primteiler $p$ von $c$ gilt, dass $p-1$ die Zahl $c-1$ teilt.

Beispiel

1105\

ist das Produkt von

5\

,

13\

und

17\

. Da

1105\

eine Carmichael-Zahl ist, gilt nach dem Satz von Korselt:

${\frac {1104}{4}}=276$	$\Rightarrow 4\$ teilt $1104\$
${\frac {1104}{12}}=92$	$\Rightarrow 12\$ teilt $1104\$ und
${\frac {1104}{16}}=69$	$\Rightarrow 16\$ teilt $1104\$ .

Pseudoprim zu allen zu c teilfremden Basen a

Unter den fermatschen Pseudoprimzahlen ist sie die Königin, denn für sie gilt, mit jeder natürlichen Zahl $a\geq 2$ , zu der die Carmichael-Zahl $c\$ teilerfremd ist,

a^{c-1}\equiv 1{\pmod {c}}

.

Beispiel

Die Zahl

561=3\cdot 11\cdot 17

ist eine Carmichael-Zahl.

Die Zahlen

43\

,

49\

und

65\

sind teilerfremd zur

561\

, also gelten:

43^{560}\equiv 1\mod 561

49^{560}\equiv 1\mod 561

65^{560}\equiv 1\mod 561

Die Zahlen

51\

,

55\

und

57\

sind nicht teilerfremd zur

561\

, also gelten:

51^{560}\not \equiv 1\mod 561

55^{560}\not \equiv 1\mod 561

57^{560}\not \equiv 1\mod 561

Carmichael-Zahlen generieren

Es gibt zwei Wege, an Carmichael-Zahlen zu kommen. Der eine ist, sich zufällig natürliche Zahlen zu erzeugen, um dann auf $a^{c-1}\equiv 1{\pmod {c}}$ und $\operatorname {ggT} (a,c)=1$ für alle $2\leq a\leq c-2$ zu testen. Die Wahrscheinlichkeit, auf diese Weise Carmichael-Zahlen zu finden ist sehr gering. Will man allerdings Carmichael-Zahlen vermeiden, so ist dieser Weg vorzuziehen. Der andere Weg ist, konsequent das Produkt aus mindestens drei, zueinander teilerfremden Primzahlen zu bilden, um die so erzeugten Zahlen auf das Korselt-Kriterium zu prüfen.

Nicht jedes quadratfreie Produkt aus Primzahlen kann eine Carmichael-Zahl sein. Ansonsten gäbe es jede Menge Carmichael-Zahlen. Aber kann man bestimmte Primzahlkombinationen schon vorher ausschließen? Man kann! Es gilt nämlich, dass zwei natürliche Zahlen $n\$ und $n-1\$ zueinander teilerfremd sind. Das bedeutet, dass $n\$ und $n-1\$ keine gemeinsamen Teiler besitzen.

Es ist also wichtig, dass bei der generierten Zahl $n=p_{1}\cdot p_{2}\cdot p_{3}\cdot ...p_{n}$ alle $p_{i}\$ zu allen $p_{j}-1\$ teilerfremd sind. Das ist nicht selbstverständlich, wie das folgende Beispiel zeigt:

5\cdot 11\cdot 23\cdot 47=59455

Wichtig an dem Beispiel ist, dass (11-1) durch 5 teilbar ist, (23-1) durch 11 und (47-1) durch 23. Ein solches Produkt kann keine Carmichael-Zahl sein.

Wenn also die Primzahl $p_{i}\$ Teiler einer Carmichael-Zahl sein soll, so sind alle Primzahlen der Form $m\cdot p_{i}+1$ als Teiler der Carmichael-Zahl ausgeschlossen.

$p_{i}$	$m\cdot p_{i}+1$
3	7	13	19	31	37	43	61	67	73	79	...
5	11	31	41	61	71	101	...
7	29	43	71	...

Carmichael-Zahlen nach Chernick

Wenn man sich auf eine spezielle Form der Carmichael-Zahlen beschränken will, dann gibt es noch die Carmichael-Zahlen nach Chernick. Diese haben die allgemeine Form:

M_{k}(m)=(6m+1)(12m+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}m+1)

wobei alle Faktoren Primzahlen sind, und für k > 4 die Zahl $m\$ durch $2^{k-4}\$ teilbar sein muss.

Für $M_{k}(3)\$ lautet die Formel $(6m+1)\cdot (12m+1)\cdot (18m+1)\$ , die äquivalent zu der Formel $p\cdot (2p-1)\cdot (3p-2)\$ für $p>3\$ ist.

Für $M_{k}(4)\$ lautet die Formel $(6m+1)\cdot (12m+1)\cdot (18m+1)\cdot (36m+1)\$ .

Beweis der Äquivalenz

Warum sind die beiden Konstruktionsvorschriften:

Eine Zahl $M_{3}(m)=(6m+1)(12m+1)(18m+1)$ ist dann eine Carmichael-Zahl,
wenn alle 3 Faktoren $(6m+1)$ , $(12m+1)$ und $(18m+1)$ Primzahlen sind.

und

Sei p > 3 eine Primzahl derart, dass auch 2p-1 und 3p-2 Primzahlen sind,
dann ist n = p(2p-1)(3p-2) eine Carmichael-Zahl

zueinander äquivalent? Es wäre doch möglich, das eine Primzahl $p\$ , die nicht der Form $6m+1\$ entspricht, existiert, so daß $2p-1\$ und $3p-2\$ auch Primzahlen sind. Nun, so eine Primzahl existiert nicht.

Es gibt nur zwei Arten von Primzahlen $p\$ mit $p>3\$ , nämlich Primzahlen der Form $6m+1\$ und Primzahlen der Form $6m-1\$ . Wenn man $p\$ durch $6m-1\$ ersetzt, bekommt man statt $2p-1\$ den Ausdruck $2(6m-1)-1\$ . Ausmultipliziert und zusammengefaßt macht das $12m-3\$ . Dieser Ausdruck ist also stets durch drei teilbar. Nur mit einer Primzahl der Form $6m+1\$ kann man mit der Formel $p\cdot (2p-1)\cdot (3p-2)\$ für $p>3\$ eine Carmichael-Zahl bekommen.

Absolute eulersche Pseudoprimzahlen

Eine absolute eulersche Pseudoprimzahl ist eine Carmichael-Zahl, die zu jeder, zu ihr teilerfremden, Basis $a$ euler-pseudoprim ist.

Für jeden Primteiler $p_{i}\$ einer absoluten Eulerschen Pseudoprimzahl $n\$ gilt:

p_{i}-1\

teilt

{\frac {n-1}{2}}\

.

Die ersten absoluten Eulerschen Pseudoprimzahlen sind 1729, 2465, 15841, 41041, 46657, 75361.

Es gibt keine absoluten Euler-Jacobi-Pseudoprimzahlen.

Häufigkeit und Überschneidung mit Lucas-Pseudoprimzahlen

Anzahl der Carmichael-Zahlen und Überschneidung
mit starken und Lucas-Pseudoprimzahlen
				gleichzeitig Carmichael- &
Obergrenze x	Carmichael^[1]	f(x)^(I)	abs epsp	sPsp(2)	lpsp	Lucas3(7,*)
10³	1	0.014	0	0	0	0
10⁴	7	0.072	2	0	0	0
10⁵	16	0.054	6	3	0	0
10⁶	43	0.047	16	5	0	0
10⁷	105	0.050	45	11	0	0
10⁸	255	0.042	124	19	0	0
10⁹	646	0.036	306	43	0	0
10¹⁰	1547	0.031	740	87	0	0
10¹¹	3605	0.024	1736	171	0	0
10¹²	8241	0.019	4011	316	0	0
10¹³	19279	0.015	9362	621	0	0
10¹⁴	44706	0.012	21974	1153	0	0
10¹⁵	105212	0.009	52221	2234	0	0
10¹⁶	246683	0.007	122608	4185	0	0

^(I)Mittlerer Anteil falscher Zeugen beim Miller-Rabin-Test.

Quellen

↑ http://www.s369624816.websitehome.co.uk/rgep/cartable.html Tables of Carmichael numbers

Fermatsche Pseudoprimzahlen

Eulersche Pseudoprimzahlen

Pseudoprimzahlen

Eine Pseudoprimzahl $q\$ , die zu irgendeiner natürlichen Zahl $a\$ pseudoprim im Sinne des kleinen fermatschen Satz ist, zu konstruieren, ist recht einfach. Man nehme zwei beliebige Primzahlen $\ p_{i}\$ mit $\ p_{i}\geq 3$ , und multipliziere sie miteinander. Das Produkt wird dann schon zu mindestens einer natürlichen Zahl $a\$ pseudoprim sein. Aber zu welcher Zahl $a$ ?

$a\$ und $\ q\$ müssen zueinander teilerfremd sein

Damit eine zusammengesetzte Zahl $\ q\$ zu einer natürlichen Zahl $a\$ pseudoprim sein kann, muss immerhin sichergestellt sein, dass $a\$ und $q\$ zueinander teilerfremd sind. Zu jeder solchen Fermatschen Pseudoprimzahl der Form $q=p_{1}\cdot p_{2}\$ lassen sich zwei Basen $a\$ finden, und zwar durch folgende Vorgehensweise:

Man ermittelt die Vielfachen von

p_{1}\

und

p_{2}\

:

p_{1},\ 2\cdot p_{1},\ 3\cdot p_{1},\ 4\cdot p_{1},\ 5\cdot p_{1},...

und

p_{2},\ 2\cdot p_{2},\ 3\cdot p_{2},\ 4\cdot p_{2},\ 5\cdot p_{2},...

Dann sucht man jeweils ein Vielfaches $m\cdot p_{1}$ und $n\cdot p_{2}$ heraus, für die $|m\cdot p_{1}-n\cdot p_{2}|=2$ gilt. Die zwischen $m\cdot p_{1}$ und $n\cdot p_{2}$ liegende Zahl ist eine Basis, zu der die Zahl $q=p_{1}\cdot p_{2}$ pseudoprim ist (im Sinne des kleinen fermatschen Satzes), und sie ist teilerfremd zu $p_{1},\ p_{2},\ m$ und $n\$ . Es gibt zu jeder Zahl $q=p_{1}\cdot p_{2}$ genau zwei Basen $a$ , die sich auf diese Weise finden lassen und kleiner als $q\$ sind. Die Summe dieser beiden Basen $\ a_{1}\$ und $\ a_{2}\$ ist $\ q$ . Alle Basen $a\$ , die größer als $q\$ sind und sich nach dem beschriebenen Algorithmus konstruieren lassen, haben entweder die Form $a=a_{1}+m\cdot q$ oder $a=a_{2}+m\cdot q$ .

Das Produkt $(a-1)(a+1)=(a^{2}-1)\$ ist immer pseudoprim zur Basis $a$ , wenn $a=2k>3$ ist, auch wenn $a+1$ oder $a-1$ zusammengesetzt ist.

Beweis:
${\begin{aligned}a^{(a+1)(a-1)-1}&=a^{a^{2}-2}\\&=a^{(2k)^{2}-2}\\&=(a^{2})^{2k^{2}-1}\\&=((a^{2}-1)+1)^{2k^{2}-1}\\&\equiv 1^{2k^{2}-1}\equiv 1{\pmod {(a^{2}-1)}}\equiv 1{\pmod {((a+1)(a-1))}}\end{aligned}}$

Beispiel

$391=17\cdot 23$

Die Vielfachen von $17\$ sind: $17,\ 34,\ 51,\ 68,\ 85,\ 102,\ 119,\ 136,\ 153,\ 170,\ 187,\ 204,\ 221,\ 238,\ 255,\ 272,\ ...$

Die Vielfachen von $23\$ sind: $23,\ 46,\ 69,\ 92,\ 115,\ 138,\ 161,\ 184,\ 207,\ 230,\ 253,\ 276,\ ...$

Von diesen Vielfachen haben $136\$ und $138\$ beziehungsweise $253\$ und $255\$ eine Differenz von $2\$ . Die zwischen $136\$ und $138\$ liegende Zahl $137\$ und die zwischen $253\$ und $255\$ liegende Zahl $254\$ sind Basen zu denen die Zahl $391\$ pseudoprim ist.

Die Summe von $137\$ und $254\$ ist $391\$ .

Pseudoprimzahlen

Mit folgendem Verfahren hat der Mathematiker Lehmer gezeigt, dass unendlich viele fermatsche Pseudoprimzahlen existieren müssen:

Man nimmt eine natürliche Zahl

k

, die größer oder gleich 5 ist. Mit dieser Zahl

k\

bildet man die beiden Zahlen

2^{k}-1\

und

2^{k}+1

. Von diesen beiden Zahlen nimmt man jeweils einen Primfaktor. Also je eine Primzahl

p\

und

q

, so dass gilt:

p\

teilt

2^{k}-1\

und

q\

teilt

2^{k}+1

. Das Produkt

p\cdot q

ist dann eine fermatsche Pseudoprimzahl zur Basis

2^{k}

.

Beispiel

Man nimmt $k=6$ : $2^{k}\pm 1$ ist dann $2^{6}-1=63=3^{2}\cdot 7$ und $2^{6}+1=65=5\cdot 13$ . Wenn man jetzt $p=7\$ und $q=5\$ wählt, bekommt man mit $5\cdot 7$ die Zahl 35, eine fermatsche Pseudoprimzahl zur Basis 64.

k	2^k-1	2^k+1	Pseudoprimzahlen nach Lehmer
5	31	3·11	93, 341
6	3²·7	5·13	15, 35, 39, 91
7	127	3·43	381, 5461
8	3·5·17	257	771, 1285, 4369
9	7·73	3³·19	21, 133, 219, 1387
10	3·11·31	5²·41	15, 55, 123, 155, 451, 1221
11	23·89	3·683	69, 267, 15709, 60787
12	3²·5·7·13	17·241	51, 85, 119, 221, 723, 1205, 1687, 3133
...	...	...	...

Pseudoprimzahlen

Dieses Kapitel oder dieser Abschnitt ist unverständlich formuliert. Ein Hinweis, was nicht verstanden wird, ist möglicherweise auf der Diskussionsseite des Artikels zu finden. Wenn Sie Hilfe benötigen, schauen Sie, welche Qualitätskriterien an ein gutes Buch gestellt werden. Das allgemeine Vorgehen bei diesem Baustein kannst Du hier nachlesen.

Fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

Michele Cipolla hat 1904 ein Verfahren zum Erzeugen beliebiger fermatscher Pseudoprimzahlen zu einer beliebigen, natürlichen Basis $a\geq 2\$ gefunden. Dazu benötigt man eine Primzahl, die $a(a^{2}-1)\$ nicht teilt. Warum, das wird weiter unten erklärt.

Mit der Basis $a\$ und der Primzahl $p\$ werden zwei Zahlen $n_{1}\$ und $n_{2}\$ erzeugt:

n_{1}={\frac {a^{p}-1}{a-1}},\ \ n_{2}={\frac {a^{p}+1}{a+1}}

Das Produkt $n=n_{1}\cdot n_{2}\$ ist eine fermatsche Pseudoprimzahl zur Basis $a\$

Erklärung

Die Bedingung, dass $p\$ teilerfremd zu $a(a^{2}-1)\$ sein soll, kann auch so formuliert werden: $p\$ soll eine Primzahl sein, die $(a-1)\cdot a\cdot (a+1)\$ nicht teilt, da nach der dritten binomischen Formel $(a^{2}-1)=(a-1)\cdot (a+1)\$ ist. Damit ist sichergestellt, dass $p\$ zu $a$ , $(a-1)\$ und $(a+1)\$ teilerfremd ist.

${\frac {a^{p}-1}{a-1}}$ und ${\frac {a^{p}+1}{a+1}}$ sind beides Partialsummen geometrischer Reihen, nämlich:

{\frac {a^{p}-1}{a-1}}=a^{p-1}+a^{p-2}+...+a^{2}+a+1

und

{\frac {a^{p}+1}{a+1}}=(-a)^{p-1}+(-a)^{p-2}+...+(-a)^{2}+(-a)+1

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 zu jeder Basis a geben.

Liste fermatscher Pseudoprimzahlen zur Basis a nach Michele Cipolla

a	p	n₁	n₂	n=n₁•n₂	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

Die Zeisel-Zahl ist eine nach dem Mathematiker Helmut Zeisel benannte Zahl, die das Produkt wenigstens dreier Primzahlen ist, die einer bestimmten linearen Rekursion genügen. Eine besondere Bedeutung in der Mathematik haben sie nicht. Auf Grund gewisser Ähnlichkeiten mit den Carmichael-Zahlen sind sie hier aufgeführt.

Definition

p₀ = 1

p_n = a·p_n-1 + b

Dabei muss jedes p_n mit $n\geq 1$ eine Primzahl ergeben, und sowohl a als auch b sind für alle p_n konstant. Die Zeisel-Zahl z ist dann das Produkt $p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$ .

Beispiel an der Zeisel-Zahl 1885

In diesem Beispiel ist a = 2 und b = 3.

p₀ = 1
p₁ = a·p₀ + b = 2·1  + 3 = 5
p₂ = a·p₁ + b = 2·5  + 3 = 13
p₃ = a·p₂ + b = 2·13 + 3 = 29

z = p₁ · p₂ · p₃ = 5 · 13 · 29 = 1885

Zusammenhang zwischen den Zeisel-Zahlen und den Carmichael-Zahlen nach J.Chernick

Die Bildungsregel der Carmichael-Zahlen nach J. Chernick lautet (6n+1)*(12n+1)*(18n+1). Diese Bildungsregel ist identisch mit der Bildungsregel für Zeisel-Zahlen mit einem a=1 und b=6n. Demzufolge sind alle Carmichael-Zahlen nach Chernick, die ein Produkt aus drei Primzahlen bilden, auch Zeisel-Zahlen.

Eine Liste von Zeisel-Zahlen

Die Carmichael-Zahlen sind fett geschrieben.

a	b	z_n
1	2	105	357
4	-1	1419	31143
1	6	1729	71319
2	3	1885	51329
3	2	4505	51753
2	5	5719	71943
10	-7	15387	323223
2	9	24211	113171
6	-1	25085	529173
4	3	27559	731127
13	-10	31929	329367
8	-3	54205	537293
3	8	59081	1141131
2	3	114985	51329*61
25	-22	207177	3531303
5	6	208681	1161311
9	-2	233569	761547
28	-25	287979	3591627
1	36	294409	3773109
6	5	336611	1171431
5	8	353977	1373373
17	-12	448585	5731229

a	b	z_n
34	-31	507579	3712383
15	-8	982513	7971447
9	2	1012121	11101911
23	-18	1073305	5972213
8	5	1242709	13109877
49	-46	1485609	31014903
55	-52	2089257	31136163
12	-1	2263811	111311571
4	27	2953711	31151631
33	-28	3077705	51374493
14	-3	3506371	111512111
2	9	3655861	113171*151
36	-31	3973085	51495333
2	59	4648261	61181421
4	33	5069629	37181757
2	65	6173179	67199463
42	-37	6253085	51737229
11	6	6985249	171932129
8	15	7355239	231991607
2	69	7355671	71211491
10	9	7558219	191991999
4	39	8011459	43211883

a	b	z_n
88	-85	8413179	317915667
6	25	8444431	312111291
47	-42	8712985	51939029
48	-43	9271805	51979413
20	-9	9773731	112114211
57	-52	15411785	523313229
3	68	18175361	71281911
5	42	18578113	472771427
6	35	19827641	412811721
9	20	20771801	292812549
3	8	23691481	1141131*401
68	-63	26000605	527718773
5	48	26758057	533131613
10	21	34179391	313313331
14	9	35347159	233314643
77	-72	37605385	531324029
20	-3	38596273	173376737
2	125	42501439	127379883
15	8	43055057	233535303
83	-78	46999705	533727893
8	35	49982899	433793067
3	98	52691801	1014011301

a	b	z_n
2	135	53399449	137409953
30	-17	54177877	1337311173
3	100	55902529	1034091327
1	210	56052361	211421631
9	34	69207769	434213823
65	-58	71550913	739725747
18	5	72730439	234197547
11	26	76724569	374334789
10	33	92835667	434634663
2	165	96916279	1674991163
6	65	104966471	714913011
1	270	118901521	271541811
8	-1	126893905	537293*2341
4	105	133800661	1095412269
29	-10	161164441	1954115679
1	306	172947529	307613919
3	148	177055201	1516011951
15	22	185245273	375778677
5	98	199708657	1036133163
4	123	212122639	1276312647
1	330	216821881	331661991
16	21	222931549	376139829

Geschichte

Der Name "Zeisel-Zahl" wurde vermutlich von Kevin Brown eingeführt, der Zahlen $k$ suchte, für die der Ausdruck $2^{k-1}+k$ eine Primzahl ergibt. In einem Posting in die Usenet-Newsgroup sci.math vom 24. Februar 1994 lieferte Helmut Zeisel die Zahl 1885 als eine weitere Lösung. Später wurde (durch Kevin Brown?) entdeckt, dass die Primfaktoren von 1885 die oben beschriebenene Eigenschaft haben. Ein Name der Art Brown-Zeisel-Zahlen wäre daher passender.

Verallgemeinerung

Man muss sich bei der Bildung der Zeisel-Zahl nicht auf $p_{0}=1$ beschränken. Auch davon abweichende Werte sind möglich.

Beispiele

$p_{0}=4,\ a=2,\ b=5$

p₀ = 4
p₁ = a·p₀ + b = 2·4  + 5 = 13
p₂ = a·p₁ + b = 2·13 + 5 = 31
p₃ = a·p₂ + b = 2·31 + 5 = 67

z = p₁ · p₂ · p₃ = 13 · 31 · 67 = 27001

$p_{0}=-1,\ a=8,\ b=27$

p₀ = -1
p₁ = a·p₀ + b = 8·-1   + 27 =   19
p₂ = a·p₁ + b = 8·19   + 27 =  179
p₃ = a·p₂ + b = 28·179 + 27 = 1459

z = p₁ · p₂ · p₃ = 19 · 179 · 1459 = 4962059

$p_{0}=13,\ a=10,\ b=9$

p₀ = 13
p₁ = 139
p₂ = 1399
p₃ = 13999
p₄ = 139999
p₅ = 1399999

z = 139 · 1399  · 13999 · 139999 · 1399999 = 533558677367032199539

Weblinks

_{Quelle: Die Zeisel-Zahlen sind aus dem Artikel Zeisel-Zahl der deutsprachigen de.wikipedia.org entnommen.}

Pseudoprimzahlen

Carmichael-Zahlen

Ein Programm, das eine Liste von Carmichael-Zahlen ausgibt, ist geradezu trivial. Dass dem so ist, verdanken wir dem Kriterium von Korselt. Dieses Theorem besagt, dass eine Carmichel-Zahl $c\$ eine quadratfreie, aus mindestens drei Primfaktoren bestehende, natürliche Zahl der Form $c=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}\$ ist, so dass für jedes $p_{i}\$ gilt, dass $p_{i}-1\$ die Zahl $c-1\$ teilt. Daraus folgt, dass man sich um den kleinen Fermatschen Satz $a^{n-1}\equiv 1{\pmod {n}}$ nicht im geringsten zu kümmern braucht. Neben Korselts Kriterium gibt es auch noch Formeln zum Erzeugen spezieller Carmichael-Zahlen. Auch bei diesen Beispielen braucht man sich um den kleinen Fermatschen Satz nicht zu kümmern.

zweiter Ansatz

Das folgende Programm benutzt drei ineinander verschachtelte Schleifen, durch die sichergestellt wird, dass drei zueinander teilerfremde Primzahlen ausgewählt werden. Aus diesen drei Primzahlen wird ein Produkt gebildet, das die zu testende Zahl darstellt. An dieser Zahl wird nun Korselts Kriterium getestet, was einfach ist, da dem Programm die Primteiler der zu testenden Zahl bekannt sind. Ist Korselt Kriterium erfüllt, dann handelt es sich bei der Zahl um eine Carmichael-Zahl, und die Zahl wird, samt Primzahlfaktoren als Carmichael-Zahl ausgegeben.

Details: Die Variable p.0 enthält die Anzahl der unterschiedlichen Primzahlen. In p.1 bis p.(p.0) sind die einzelnen Primzahlen abgelegt.

p.1  = 3
p.2  = 5
p.3  = 7
p.4  = 11
p.4  = 13
p.5  = 17
p.6  = 19
p.7  = 23
p.8  = 29
p.9  = 31
p.10 = 37
.
.
.
p.549 = 4001
p.550 = 4003
p.551 = 4007
p.552 = 4013
p.553 = 4019
p.554 = 4021
p.555 = 4027
p.556 = 4049
p.557 = 4051
p.558 = 4057
i=558
do a=1 to (i-2)
  do b=a+1 to (i-1)
    do c=b+1 to i
      t = 0
      z=p.a*p.b*p.c
      ax=p.a-1
      bx=p.b-1
      cx=p.c-1
      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)
      if (pz = 0) then t = 1
      if (t = 1) then do
        say z||"="||p.a||"*"||p.b||"*"||p.c
        lineout("rcrmn___.txt",z||" = "||p.a||"*"||p.b||"*"||p.c)
      end
      t=0
    end
  end
end

Das Programm kann man modifizieren, indem man die Anzahl der Primzahlen erhöht. Für Carmichael-Zahlen mit mehr als drei Primfaktoren muss man die Anzahl der Schleifen erhöhen, und die Prüfroutinen erweitern.

Carmichael-Zahlen nach Chernick

Die Carmichel-Zahlen nach Chernick sind nur ein kleiner Ausschnitt aus den Carmichael-Zahlen. Sie lassen sich durch folgende Formel generieren: $M_{3}(n)=(6n+1)\cdot (12n+1)\cdot (18n+1)\$ . Es gibt dabei allerdings eine Einschränkung:

Jeder der drei Faktoren $(6n+1)\$ , $(12n+1)\$ und $(18n+1)\$ muss eine Primzahl sein. Halt, hier gibt es eine Ausnahme: Wenn ein einziger der drei Faktoren selbst eine Carmichael-Zahl ist, so ist $M_{3}(n)\$ trotzdem eine Carmichael-Zahl.

Da alle Carmichael-Zahlen quadratfrei sind, ist dann auch jeder der drei Faktoren $(6n+1)$ , $(12n+1)\$ und $(18n+1)\$ quadratfrei - auch wenn einer davon eine Carmichael-Zahl ist. Da die drei Faktoren paarweise teilerfremd sind, ist auch der Ausdruck $M_{3}(n)=(6n+1)\cdot (12n+1)\cdot (18n+1)\$ quadratfrei.

Alle gültigen $n\$ für Carmichael-Zahlen nach Chernick enden im Dezimalsystem mit einer 0, einer 1 einer 5 oder einer 6.

l.1  = 0
l.2  = 1
l.3  = 5
l.4  = 6
do i = 0 to 1000
  do j = 1 to 4
    n=i+l.j
    m=(6*n+1)*(12*n+1)*(18*n+1)
    if((primzahl(6*n+1)=true) && (primzahl(12*n+1)=true) && (primzahl(18*n+1)=true)) then do
      say m||"="||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1)
      lineout("rcrmn___.txt",m||" = "||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1))
    end
  end
end

Das Programm lässt sich entsprechend der Formeln für Carmichael-Zahlen nach Chernick, mit mehr als drei Primzahlfaktoren, nach der entsprechenden Formel erweitern.

Absolute Eulersche Pseudoprimzahlen

Das Programm, mit dem oben Carmichael-Zahlen erzeugt werden, kann man mit einer kleinen Modifikation dazu bringen, absolute eulersche Pseudoprimzahlen zu erzeugen:

      zax=(z-1)/2
      pz=(zax // ax) + (zax // bx) + (zax // cx)

statt

      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)

Das hierbei alle absoluten eulerschen Pseudoprimzahlen ausgegeben werden, ist eine andere Frage. Aber die Zahlen, die ausgegeben werden, sind absolute Eulersche Pseudoprimzahlen.

Modulare Arithmetik

Da man es bei der Berechnung von fermatschen Pseudoprimzahlen häufig mit großen Potenzen großer Zahlen zu tun bekommt, hat man ein kleines Problem. Zum Beispiel für den Nachweis, dass 341 eine fermatsche Pseudoprimzahl zur Basis 2 ist, muss man die Zahl $2^{340}\$ berechnen. Diese Zahl heißt ausgeschrieben:

2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776

Das ist für ein Programm wie MuPad wahrscheinlich kein Problem, für die meisten herkömmlichen Programmiersprachen aber sehr wohl. Durch eine Kombination von Multiplikation und Modulo kann man aber auch wesentlich größere Potenzen kleinhalten.
Da bei Rechenoperationen Modulo $n$ nur Zahlen bis $\ n-1\$ auftreten, ist das Ergebnis einer Multiplikation vor der Modulooperation immer kleiner als $n^{2}$ .

Beispiel: $5^{6}=15625$ . Letztendlich interessiert uns ja aber nicht $5^{6}=15625\$ , sondern vielmehr $5^{6}\operatorname {mod} n$ mit sagen wir mal $n=7$ . Das ist $5^{6}\operatorname {mod} 7=1\$ . Nun lässt sich $5^{6}\operatorname {mod} 7\$ auch so berechnen:

(((((((((5*5)\operatorname {mod} 7)*5)\operatorname {mod} 7)*5)\operatorname {mod} 7)*5)\operatorname {mod} 7)*5)\operatorname {mod} 7

Dabei wird der Wert 7 niemals überschritten.

/* REXX-Programm */
say 'Only a Library!'
exit 1
/* */
/* */
m_u: procedure
  arg a,l,m
/* initialisierung */
  as = a
  ai = a
  li = (l-1)
  DO li
    a = a * ai
    a = a // m
  END
return a

Binäres Potenzieren

Für Primzahltests nach dem kleinen fermatsche Satz müssen große Potenzen berechnet werden; dabei wäre es extrem zeitaufwendig, x^k durch k - 1 Multiplikationen zu berechnen. Ein effiziente Berechnung ist durch binäre Exponentiation möglich:

Gegeben seien die Basis x und der Exponent k.

Berechnungsschritte:
setze P = 1 (Produkt) und b = x
wiederhole folgende Schritte solange k > 0 ist:
	wenn k ungerade ist, multipliziere P mit b → P und vermindere k um 1 → k	P = P * b k = k - 1
	quadriere b → b	b = b * b
	halbiere k → k	k = k / 2
Ergebnis: P = x^k, wenn k = 0 ist

Bei Berechnung Modulo $n$ wird das Ergebnis jeder Multiplikation mod $n$ reduziert, wie im vorherigen Absatz beschrieben.

Insgesamt sind mit dieser Methode nur maximal 2 Multiplikationen pro Bit des Exponenten notwendig, also $2\cdot \lceil log_{2}k\rceil$ .

Liste zusammengesetzter Zahlen

Um Primzahltests zu prüfen bzw. Pseudoprimzahlen zu finden, wäre eine Funktion, die eine Liste (ungerader) zusammengesetzter Zahlen erstellt, nützlich. Sie spart zum einen die Überprüfung aller Zahlen, die den Test bestehen, mit einem im untersuchten Zahlenbereich sicheren Primzahltest, um Pseudoprimzahlen von Primzahlen zu unterscheiden, und zum anderen werden Primzahlen von vornherein nicht getestet.

Mit einem Algorithmus, der wie das Sieb des Eratosthenes funktioniert, lässt sich ein solches Hilfmittel realisieren:

Erstelle eine leere Menge für das Ergebnis
Für alle ungeraden n von 3 bis Obergrenze:
- wenn n nicht in der Menge enthalten ist:
  - nimm alle ungeraden Vielfachen von n (n² + 2k*n) von n² bis zur Obergrenze in die Menge auf
Sortiere die Elemente der Menge aufsteigend

Implementierung in Python

def odd_composites(lim):
    result = set()
    for n in range(3, lim, 2):
        if n not in result:
            for m in range(n*n, lim, 2*n):
                result.add(m)
    return sorted(result)

Die Funktion lässt sich leicht so erweitern, dass auch gerade Zahlen zurückgegeben werden; diese sind aber für Primzahltests weniger interessant.

Fermatsche Pseudoprimzahlen

Bei Primzahlen ist im Gegensatz zu fermatschen Pseudoprimzahlen und Carmichael-Zahlen die Kongruenz $a^{n-1}\equiv 1{\pmod {n}}$ für alle Basen $a\$ mit $2\leq a<n$ erfüllt. Carmichael-Zahlen unterscheiden sich von anderen fermatschen Pseudoprimzahlen dadurch, dass der Anteil der Primbasen $a\$ mit $2\leq a<n$ , für die $a^{n-1}\equiv 1{\pmod {n}}$ ist, größer als 97% ist. Der Einfachheit halber benutzt man als Basen $a\$ nur die Primzahlen, die kleiner als die zu testende Zahl $n\$ sind. Das Programm testet also zu jeder Primbasis $a\$ , ob eine Zahl $n\$ die Bedingung $a^{n-1}\equiv 1{\pmod {n}}$ erfüllt. Erfüllt sie sie, wird die Variable tm1 = 1 gesetzt und gleichzeitig die Zählvariable tm3 um eins erhöht. Erfüllt die Zahl $n\$ die Bedingung nicht, wird die Variable tm2 = 2 gesetzt. Nach Ablauf der Tests wird die Variable gtm = tm1 + tm2 gesetzt. Aus gtm und dtm lässt sich ablesen, ob es sich bei der Zahl $n\$ um eine Primzahl, eine fermatsche Pseudoprimzahl oder eine Carmichael-Zahl handelt.

gtm	dtm	Art der Zahl
1	-	Primzahl
3	tm3 < dtm	fermatsche Pseudoprimzahl
3	tm3 >= dtm	Carmichael-Zahl

/* Ein Programm zur Ermittlung von Primzahlen, Pseudoprimzahlen */
/* und Carmichaelzahlen   */
/* Ein langsames Programm */

#include <stdio.h>

int primfeld[400000];
int tst[400000];

unsigned long modup(unsigned long base, unsigned long y)
{
  unsigned long exponent, product = 1;
  exponent = y-1;
  while (exponent)
  {
    /* wenn Exponent gerade ist, Basis quadrieren und Exponent halbieren bis der Exponent ungerade ist: */
    while (exponent & 1 == 0)
    {
      exponent >>= 1;
      base = (base * base) % y;
    }
    /* Exponent ungerade (immer nach obiger Schleife): Produkt *= Basis ... %= y, Exponent dekrementieren: */
    product = (product * base) % y;
    exponent--;
  }
  return(product);
} 

int main()
{
  unsigned long index, index2, anzp=1, m, dtm;
  int tm1, tm2, tm3, gtm;
  FILE *prim;
  FILE *pspr;
  FILE *cnbr;
  prim = fopen("prim.dat","w");
  pspr = fopen("pspr.dat","w");
  cnbr = fopen("cnbr.dat","w");
  primfeld[1] = 2;
  for(index=3;index<=4000000;index++)
  {
    tm1 = 0;
    tm2 = 0;
    tm3 = 0;
    /* faktor$ = "" */
    for(index2=1;index2<=anzp;index2++)
    {
      m = modup(primfeld[index2], index);
      tst[index2] = m;
      if (m == 1)
      {
        tm1 = 1;
        tm3++;
      }
      if ( m != 1) { tm2 = 2; }
    }
    gtm = tm1 + tm2;
    if (gtm == 1)
    {
      anzp++;
      primfeld[anzp] = index;
      fprintf(prim,"%d \n",index);
    }
    if (gtm == 3)
    {
      dtm=anzp/2;
      if (tm3 < dtm)
      {
        fprintf(pspr,"%d: ",index);
        for(index2=1;index2<=anzp;index2++)
        {
          m = modup(primfeld[index2], index);
          if (m == 1)
          {
            fprintf(pspr,"%d, ",primfeld[index2]);
          }
        }
        fprintf(pspr,"\n",0);
      }
      if (tm3 >= dtm)
      {
        fprintf(pspr,"%d: ",index);
        for(index2=1;index2<=anzp;index2++)
        {
          m = modup(primfeld[index2], index);
          if (m != 1)
          {
            fprintf(cnbr,"N%d, ",primfeld[index2]);
          }
        }
        fprintf(cnbr,"\n",0);
      }
    }
  }
  fclose(prim);
  fclose(pspr);
  fclose(cnbr);
  return 0;
}

Nachteil des Programms: Es wird schnell sehr langsam. Außerdem ist es für einige Pseudoprimzahlen blind. So gibt es keine Primzahlen $p<39$ , zu denen die 39 pseudoprim ist.

Pseudoprimzahlen

Der kleine Fermatsche Satz besagt, dass $\ a^{p}-a\$ für jede Primzahl $\ p\$ und jede natürliche Zahl $a\geq 2\$ durch $\ p\$ teilbar ist.

Beispiel anhand der Primzahl 5:

$2^{5}-2=5\cdot 6$
$3^{5}-3=5\cdot 48$
$4^{5}-4=5\cdot 204$

Ableitungen

Statt der Aussage: " $a^{p}-a\$ ist (ohne Rest) durch $\ p\$ teilbar", kann man auch $\ a^{p}\equiv a{\pmod {p}}\$ schreiben. Wenn man $a\$ aus $a^{p}-a\$ ausklammert, kommt man auf einen Ausdruck $a\cdot (a^{p-1}-1)$ . Da $a\cdot (a^{p-1}-1)\$ durch $\ p\$ teilbar ist, aber $\ a\$ nicht zwangsläufig durch $p\$ teilbar ist, muss es der Ausdruck $(a^{p-1}-1)\$ sein, der immer durch $p\$ teilbar ist. Aus der Aussage: " $a^{p-1}-1\$ ist durch $p\$ teilbar", kann man $a^{p-1}\equiv 1{\pmod {p}}$ ableiten. Die Aussage: " $a^{p-1}-1\$ ist durch $p\$ teilbar" und die Formel $a^{p-1}\equiv 1{\pmod {p}}$ gelten allerdings nur, wenn die Basis $\ a\$ teilerfremd zur Primzahl $\ p\$ ist.

Was unterscheidet aⁿ ≡ a (mod n) von a^n-1 ≡ 1 (mod n)

Für jede Primzahl $p\$ gilt, dass für jede natürliche Zahl $a\$ der Ausdruck $a^{p}-a\$ durch $p\$ teilbar ist. Ebenso gilt für jede Carmichael-Zahl $c$ , dass für jede natürliche Zahl $a\$ der Ausdruck $a^{c}-a\$ durch $c\$ teilbar ist.

Ja aber bitte wie unterscheidet man dann eine Primzahl von einer Carmichael-Zahl?

Es gibt natürlich noch andere Wege, um das Problem anzugehen, aber dafür hilft auch eine Modifikation des kleinen Fermatschen Satzes:

Für jede Primzahl

p\

gilt:

a^{p-1}\equiv 1{\pmod {p}}

für jede natürliche Zahl

a

, die teilerfremd zu

p\

ist.

Das bedeutet, dass der kleine fermatsche Satz für $a=p\$ nicht gilt: $p^{p-1}\not \equiv 1\ {\pmod {p}}$ . Ähnliches gilt für jede Carmichael-Zahl $c\$ : $c^{c-1}\not \equiv 1\ {\pmod {c}}$ . Aber es gilt genauso für alle Primteiler $p_{m}\$ der entsprechenden Carmichael-Zahl $c=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$ : $\ p_{m}^{c-1}\not \equiv 1\ {\pmod {c}}$ .

Folgerung durch Euler

Auf den kleinen Fermatschen Satz lässt sich die dritte binomische Formel $a^{2}-b^{2}=(a+b)\cdot (a-b)$ anwenden:

$a^{p-1}-1=(a^{\frac {p-1}{2}}+1)\cdot (a^{\frac {p-1}{2}}-1)\equiv 0{\pmod {p}}$ .

Das bedeutet, dass genau einer der beiden Faktoren durch $p\$ teilbar sein muss, dass also $\ a^{\frac {p-1}{2}}+1$ oder $a^{\frac {p-1}{2}}-1$ durch $p\$ teilbar ist. Das führt zu dem Satz, der Leonhard Euler zugesprochen wird:

Wenn $p\$ eine ungerade Primzahl ist, muss entweder

$a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$ oder
$a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ gelten.

Pseudoprimzahlen

Potenzen

Wenn man eine Zahl immer wieder mit sich selbst multipliziert, erhält man eine Potenz. Eine bekannte Folge von steigenden Potenzen ist die folgende Folge aus Zweierpotenzen:

2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,...\

Verallgemeinert sieht eine solche Folge für eine beliebige Basis so aus:

a,a^{2},a^{3},a^{4},a^{5},a^{6},...\

Ein Feld solcher Zahlen sieht so aus:

	1	2	3	4	5	6	7	8	9	...
a
1	1	1	1	1	1	1	1	1	1	...
2	2	4	8	16	32	64	128	256	512	...
3	3	9	27	81	243	729	2187	6561	19683	...
4	4	16	64	256	1024	4096	16384	65536	262144	...
5	5	25	125	625	3125	15625	78125	390625	1953125	...
6	6	36	216	1296	7776	46656	279936	1679616	10077696	...
7	7	49	343	2401	16807	117649	823543	5764801	40353607	...
8	8	64	512	4096	32768	262144	2097152	16777216	134217728	...
9	9	81	729	6561	59049	531441	4782969	43046721	387420489	...
10	10	100	1000	10000	100000	1000000	10000000	100000000	1000000000	...
11	11	121	1331	14641	161051	1771561	19487171	214358881	2357947691	...
12	12	144	1728	20736	248832	2985984	35831808	429981696	5159780352	...
..	..	...	...	...	...	...	...	...	...	...

Die Struktur, die dahinter steckt, wird sichtbar, wenn man das ganze Feld eine mithilfe von Modulo und einem festen Faktor unterzieht:

Beispiel: Modulo 7

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	...
1:	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
2:	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
3:	3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
4:	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
5:	5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
6:	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
7:	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
8:	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
9:	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
10:	3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
11:	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
12:	5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
13:	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
14:	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
15:	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
16:	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
17:	3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
18:	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
19:	5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
20:	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
21:	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...

Die kleinste Einheit wird durch zwei Größen festgelegt, nämlich einmal den Wert $n\$ , zu dem man das Ganze Modulo nimmt und der die Einheit nach unten begrenzt, und andererseits die Carmichael-Funktion $\lambda (n)$ , die der kleinste gemeinsame Faktor darstellt, zu der für jeden zu $n\$ teilerfremden Wert $a\$ gilt: $a^{\lambda (n)}\equiv 1\mod n$ .

Muster

Zu jeder natürlichen Zahl $n\$ gibt es ein individuelles Erscheinungsbild. Andererseits haben bestimmte Arten von Zahlen Gemeinsamkeiten. Um das, was Zahlen gemeinsam haben, geht es hier:

natürliche Zahlen

Alle natürlichen Zahlen haben eine Gemeinsamkeit in ihrer Struktur:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
A:	A	1	A	1	A	1

In der obersten Zeile befinden sich immer Einsen und in der untersten Zeile befinden sich immer im Wechsel A und 1, wobei A für $n-1\$ steht. Dies ist also keine Charakteristik, die für Primzahlen typisch ist.

Primzahlen

Die für eine Primzahl typische Struktur sieht so aus:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
A:	A	1	A	1	A	1

Zu der für jede natürliche Zahl typischen Zeilen kommen zwei Charaktaristika bei Primzahlen hinzu:

Erstens die geschlossene Einserspalte

1

...

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion $a^{\lambda (n)}$ zurückliefert.

Zweitens die, ebenfalls geschlossene, Zeile aus Einsern und Zahlen A die die Zahl (n-1) repräsentieren.

1

A

...

Hier sind es die Werte, die die nach der nach Euler modifizierten Funktion $a^{\frac {\lambda (n)}{2}}$ zurückgeliefert werden.

Unterscheidung der Primzahlen in 4k-1 und 4k+1-Form

Die Struktur von Primzahlen der Form 4k-1 und 4k+1 unterscheidet sich in einer Spalte:

	1	2	3	4	5	6	7	8	9	10
1:	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	5	10	9	7	3	6	1
3:	3	9	5	4	1	3	9	5	4	1
4:	4	5	9	3	1	4	5	9	3	1
5:	5	3	4	9	1	5	3	4	9	1
6:	6	3	7	9	10	5	8	4	2	1
7:	7	5	2	3	10	4	6	9	8	1
8:	8	9	6	4	10	3	2	5	7	1
9:	9	4	3	5	1	9	4	3	5	1
10:	10	1	10	1	10	1	10	1	10	1

	1	2	3	4	5	6	7	8	9	10	11	12
1:	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	3	6	12	11	9	5	10	7	1
3:	3	9	1	3	9	1	3	9	1	3	9	1
4:	4	3	12	9	10	1	4	3	12	9	10	1
5:	5	12	8	1	5	12	8	1	5	12	8	1
6:	6	10	8	9	2	12	7	3	5	4	11	1
7:	7	10	5	9	11	12	6	3	8	4	2	1
8:	8	12	5	1	8	12	5	1	8	12	5	1
9:	9	3	1	9	3	1	9	3	1	9	3	1
10:	10	9	12	3	4	1	10	9	12	3	4	1
11:	11	4	5	3	7	12	2	9	8	10	6	1
12:	12	1	12	1	12	1	12	1	12	1	12	1

Primzahl der Form 4k+3

Primzahl der Form 4k+1

Wie man sehen kann, ist die violette Spalte bei Primzahlen der Form 4k+1 symmetrisch und bei Primzahlen der Form 4k+3 komplementär.

Abgrenzung der Primzahlen von anderen natürlichen Zahlen

Bei allen anderen Arten natürlicher Zahlen fehlt die Geschlossenheit der beiden senkrechten Spalten.

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	8	7	5	1
3:	3	0	0	0	0	0
4:	4	7	1	4	7	1
5:	5	7	8	4	2	1
6:	6	0	0	0	0	0
7:	7	4	1	7	4	1
8:	8	1	8	1	8	1

	1	2	3	4
1:	1	1	1	1
2:	2	4	8	1
3:	3	9	2	6
4:	4	1	4	1
5:	5	10	5	10
6:	6	6	6	6
7:	7	4	13	1
8:	8	4	2	1
9:	9	6	9	6
10:	10	10	10	10
11:	11	1	11	1
12:	12	9	3	6
13:	13	4	7	1
14:	14	1	14	1

Neun

Fünfzehn

Wie man bei der Neun sehen kann, ist der Mittelbalken noch, wenn auch unterbrochen, vorhanden. Bei der 15 fehlt er vollständig.

Carmichael-Zahlen

Nachdem was bisher geschrieben worden ist, müßte die Neun, und damit alle Quadrate einer Primzahl, eine perfekte Fast-Primzahl sein. Dem ist aber nicht so. Damit eine Nichtprimzahl eine gute Fast-Primzahl sein kann, muß eines zutreffen: $n-1\$ muß durch $\lambda (n)\$ teilbar sein. Nichtprimzahlen mit dieser Eigenschaft nennt man Carmichael-Zahlen.

Was stimmt nun also an der Neun nicht? Die Einser liegen auf der blauen und, mit den Achten, auf der violetten Spalte.

Sie müßten allerdings auf der grünen Spalte liegen, und zusammen mit Achten auf der cyanen Spalte. Da ist aber weder eine Eins, noch eine Acht vorhanden. Einsen auf der grünen Spalte sind typisch für fermatsche Pseudoprimzahlen, und Einsen, bzw. (n-1) auf der cyanen Spalte sind typisch für eulersche Pseudoprimzahlen.

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	8	7	5	1
3:	3	0	0	0	0	0
4:	4	7	1	4	7	1
5:	5	7	8	4	2	1
6:	6	0	0	0	0	0
7:	7	4	1	7	4	1
8:	8	1	8	1	8	1

Die weiter oben abgebildete 15 ist eine fermatsche Pseudoprimzahl zu den Basen 4 und 11.

Folgerichtig muß man die Struktur für eine typische Primzahl ergänzen:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
A:	A	1	A	1	A	1

Pseudoprimzahlen

Selbstreferenzierende Spalte

Wie ja schon bekannt ist, gilt für eine Primzahl $p\$ , das für jede zu $p\$ teilerfremde Basis $a\$ $a^{p-1}\equiv 1\mod p$ gilt (Siehe blaue Spalte in der unteren Tabelle).

	1	2	3	4	5	6	7	8	9	10	11	12
1:	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	3	6	12	11	9	5	10	7	1
3:	3	9	1	3	9	1	3	9	1	3	9	1
4:	4	3	12	9	10	1	4	3	12	9	10	1
5:	5	12	8	1	5	12	8	1	5	12	8	1
6:	6	10	8	9	2	12	7	3	5	4	11	1
7:	7	10	5	9	11	12	6	3	8	4	2	1
8:	8	12	5	1	8	12	5	1	8	12	5	1
9:	9	3	1	9	3	1	9	3	1	9	3	1
10:	10	9	12	3	4	1	10	9	12	3	4	1
11:	11	4	5	3	7	12	2	9	8	10	6	1
12:	12	1	12	1	12	1	12	1	12	1	12	1

Nun ist $p-1\$ aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl $p=13\$ das $(p-1)=12=2\cdot 2\cdot 3$ ist, sich also z.B. in $2\cdot 6$ und $3\cdot 4$ zerlegen läßt. Das bedeutet, wenn sich ein Exponent $n\$ in zwei Faktoren $r\$ uns $s\$ zerlegen läßt, das $(a^{r})^{s}=(a^{s})^{r}=a^{r\cdot s}=a^{n}$ gilt.

Beispiele:

$(5^{3})^{4}=5^{3\cdot 4}=5^{12}$
$(5^{2})^{6}=5^{2\cdot 6}=5^{12}$

	1	2	3	4	5	6	7	8	9	10	11	12
1:	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	3	6	12	11	9	5	10	7	1
3:	3	9	1	3	9	1	3	9	1	3	9	1
4:	4	3	12	9	10	1	4	3	12	9	10	1
5:	5	12	8	1	5	12	8	1	5	12	8	1
6:	6	10	8	9	2	12	7	3	5	4	11	1
7:	7	10	5	9	11	12	6	3	8	4	2	1
8:	8	12	5	1	8	12	5	1	8	12	5	1
9:	9	3	1	9	3	1	9	3	1	9	3	1
10:	10	9	12	3	4	1	10	9	12	3	4	1
11:	11	4	5	3	7	12	2	9	8	10	6	1
12:	12	1	12	1	12	1	12	1	12	1	12	1

pure eulersche Pseudoprimzahl

Mit der puren eulerschen Pseudoprimzahl ist eine fermatsche Pseudoprimzahl gemeint, bei der jede Basis, zu der die Zahl eine fermatsche Pseuodoprimzahl ist, auch gilt, das die Zahl zu der gleichen Basis auch eine eulersche Pseudoprimzahl ist.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1:	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	16	7	14	3	6	12	24	23	21	17	9	18	11	22	19	13	1
3:	3	9	2	6	18	4	12	11	8	24	22	16	23	19	7	21	13	14	17	1
4:	4	16	14	6	24	21	9	11	19	1	4	16	14	6	24	21	9	11	19	1
5:	5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
6:	6	11	16	21	1	6	11	16	21	1	6	11	16	21	1	6	11	16	21	1
7:	7	24	18	1	7	24	18	1	7	24	18	1	7	24	18	1	7	24	18	1
8:	8	14	12	21	18	19	2	16	3	24	17	11	13	4	7	6	23	9	22	1
9:	9	6	4	11	24	16	19	21	14	1	9	6	4	11	24	16	19	21	14	1
10:	10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
11:	11	21	6	16	1	11	21	6	16	1	11	21	6	16	1	11	21	6	16	1
12:	12	19	3	11	7	9	8	21	2	24	13	6	22	14	18	16	17	4	23	1
13:	13	19	22	11	18	9	17	21	23	24	12	6	3	14	7	16	8	4	2	1
14:	14	21	19	16	24	11	4	6	9	1	14	21	19	16	24	11	4	6	9	1
15:	15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
16:	16	6	21	11	1	16	6	21	11	1	16	6	21	11	1	16	6	21	11	1
17:	17	14	13	21	7	19	23	16	22	24	8	11	12	4	18	6	2	9	3	1
18:	18	24	7	1	18	24	7	1	18	24	7	1	18	24	7	1	18	24	7	1
19:	19	11	9	21	24	6	14	16	4	1	19	11	9	21	24	6	14	16	4	1
20:	20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
21:	21	16	11	6	1	21	16	11	6	1	21	16	11	6	1	21	16	11	6	1
22:	22	9	23	6	7	4	13	11	17	24	3	16	2	19	18	21	12	14	8	1
23:	23	4	17	16	18	14	22	6	13	24	2	21	8	9	7	11	3	19	12	1
24:	24	1	24	1	24	1	24	1	24	1	24	1	24	1	24	1	24	1	24	1

	1	2	3	4	5	6	7	8	9	10
1:	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	16	32	31	29	25	17	1
3:	3	9	27	15	12	3	9	27	15	12
4:	4	16	31	25	1	4	16	31	25	1
5:	5	25	26

[lpsp-1] Lucas Pseudoprimes

[2] The pseudoprimes to 25 * 10^9

[3] On the number of false witnesses for a composite number, S. 270 (5.4)

[4] Miller-Rabin-Test

[5] Pseudoprimes and Fermat numbers

[6] Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7 http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf

[7] The pseudoprimes to 25 * 10^9

[8] Glossar

[9] Multiplicative order

[10] New Implementations for Tabulating Pseudoprimes and Liars.pdf

[11] On the number of false witnesses for a composite number, S. 270 (5.4)

[12] Primzahlsatz

[13] Pseudoprime Statistics, Tables

[14] ttp://www.s369624816.websitehome.co.uk/rgep/cartable.html Tables of Carmichael numbers

[1]

[2]

[1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[1]

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	8	7	5	1
3:	3	0	0	0	0	0
4:	4	7	1	4	7	1
5:	5	7	8	4	2	1
6:	6	0	0	0	0	0
7:	7	4	1	7	4	1
8:	8	1	8	1	8	1

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	8	7	5	1
3:	3	0	0	0	0	0
4:	4	7	1	4	7	1
5:	5	7	8	4	2	1
6:	6	0	0	0	0	0
7:	7	4	1	7	4	1
8:	8	1	8	1	8	1

Pseudoprimzahlen: Meta: Überblick

Was soll das Buch bezwecken?

Warum dieses Buch?

Für wen ist dieses Buch gedacht?

Ein rechenintensives Thema

Unterscheidung

Definition

Hintergrund

Der Umkehrschluss

Unterscheidung

Absolute Pseudoprimzahlen

Starke Pseudoprimzahlen

Ein paar Daten zu den fermatschen Pseudoprimzahlen

Definition

Anzahl der Basen

Eigenschaften

Zusammenhänge zwischen den Basen

Teiler

Ein paar Daten zu den fermatschen Pseudoprimzahlen

Quellen

Eulersche Pseudoprimzahl

Eulersche Pseudoprimzahlen sind auch Fermatsche Pseudoprimzahlen

Euler-Jacobi-Pseudoprimzahl

Anzahl der Basen

Quellen

Definition

Eigenschaften

Bezug zu Eulerschen Pseudoprimzahlen

Teiler

Anzahl der Basen

Häufigkeit

Restklassen

Beispiele

Quellen

Carmichael-Zahlen

Quadratfreiheit

mindestens drei Primfaktoren

Satz von Korselt

Pseudoprim zu allen zu c teilfremden Basen a

Carmichael-Zahlen generieren

Carmichael-Zahlen nach Chernick

Beweis der Äquivalenz

Absolute eulersche Pseudoprimzahlen

Häufigkeit und Überschneidung mit Lucas-Pseudoprimzahlen

Quellen

Beispiel

Beispiel

Fermatsche Pseudoprimzahlen zur Basis a nach Michele Cipolla

Erklärung

Liste fermatscher Pseudoprimzahlen zur Basis a nach Michele Cipolla

Definition

Beispiel an der Zeisel-Zahl 1885

Zusammenhang zwischen den Zeisel-Zahlen und den Carmichael-Zahlen nach J.Chernick

Eine Liste von Zeisel-Zahlen

Geschichte

Verallgemeinerung

Beispiele

Weblinks

Carmichael-Zahlen

zweiter Ansatz

Carmichael-Zahlen nach Chernick

Absolute Eulersche Pseudoprimzahlen

Modulare Arithmetik

Binäres Potenzieren

Liste zusammengesetzter Zahlen

Implementierung in Python

Fermatsche Pseudoprimzahlen

Ableitungen

Was unterscheidet an ≡ a (mod n) von an-1 ≡ 1 (mod n)

Folgerung durch Euler

Potenzen

Muster

natürliche Zahlen

Primzahlen

Unterscheidung der Primzahlen in 4k-1 und 4k+1-Form

Abgrenzung der Primzahlen von anderen natürlichen Zahlen

Carmichael-Zahlen

Pseudoprimzahlen

Selbstreferenzierende Spalte

pure eulersche Pseudoprimzahl

Was unterscheidet aⁿ ≡ a (mod n) von a^n-1 ≡ 1 (mod n)

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	8	7	5	1
3:	3	0	0	0	0	0
4:	4	7	1	4	7	1
5:	5	7	8	4	2	1
6:	6	0	0	0	0	0
7:	7	4	1	7	4	1
8:	8	1	8	1	8	1