Pseudoprimzahlen: Fermatsche Pseudoprimzahlen

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)$.

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.

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 2 341 3 91 4 15 5 124 6 35 7 25 8 21 9 28 10 33 11 15 12 65 13 21 14 39 15 341 16 51 17 45 18 25 19 45 20 57 21 55

a fpsp 22 69 23 33 24 115 25 28 26 45 27 65 28 45 29 35 30 49 31 49 32 93 33 85 34 55 35 51 36 91 37 45 38 65 39 95 40 91 41 105

a fpsp 42 205 43 77 44 65 45 76 46 133 47 65 48 91 49 66 50 119 51 65 52 85 53 65 54 265 55 63 56 95 57 65 58 133 59 87 60 341 61 91

a fpsp 62 91 63 341 64 85 65 112 66 91 67 85 68 91 69 85 70 169 71 105 72 85 73 111 74 91 75 91 76 105 77 247 78 341 79 91 80 169 81 85

a fpsp 82 91 83 105 84 415 85 129 86 145 87 91 88 91 89 99 90 623 91 115 92 105 93 301 94 121 95 141 96 133 97 105 98 153 99 145 100 153 101 175

a fpsp 102 133 103 133 104 145 105 451 106 133 107 133 108 341 109 117 110 259 111 190 112 121 113 133 114 205 115 133 116 195 117 145 118 121 119 177 120 187 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 muss 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 innerhalb bestimmter Grenzen mehr Pseudoprimzahlen als Primzahlen, oder verhält es sich umgekehrt?

Dabei muss man unterscheiden: Meint man die Fermatschen Pseudoprimzahlen zu einer bestimmten Basis $a$, so sind es innerhalb der gleichen 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 innerhalb der gleichen 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