Zum Inhalt springen

Pseudoprimzahlen: Perrinsche Pseudoprimzahlen

Aus Wikibooks

Die Perrin-Folge ist eine Folge natürlicher Zahlen, bei der, ähnlich wie bei der Fibonacci-Folge, jedes Glied die Summe von Vorgängergliedern ist (also eine rekursiv definierte Folge).[1]

Perrinsche Pseudoprimzahlen sind zusammengesetzte Zahlen , die teilen.

Perrin-Folge

[Bearbeiten]

Die Glieder der Perrin-Folge sind wie folgt definiert:

Aus obiger Bildungsregel folgt
;

damit kann die Folge auf negative Indizes erweitert werden.

Matrixformel

[Bearbeiten]

Beliebige Folgeglieder können mit der Matrixformel

durch binäre Exponentiation ganzzahlig berechnet werden, ohne alle zwischen 0 und k liegenden P(k) zu berechnen. Durch Exponentiation der inversen Matrix können in gleicher Weise Folgeglieder mit negativem Index berechnet werden:

Perrin-Pseudoprimzahlen

[Bearbeiten]

Alle Primzahlen teilen :

. (1)

Es gibt aber auch zusammengesetzte Zahlen , die teilen; diese werden Perrinsche Pseudoprimzahlen genannt.[2] Die ersten Perrinschen Pseudoprimzahlen sind die folgenden:
271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, 1091327579, 1133818561, 1235188597, 1389675541.

Für Primzahlen gilt auch

. (2)

Zusammengesetze Zahlen, die beide Bedingungen erfüllen, heißen eingeschränkte Perrinsche Pseudoprimzahlen. Die ersten derartigen Pseudoprimzahlen sind 27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121.[3]

Die ersten Pseudoprimzahlen, die (nur) Bedingung (2) erfüllen, sind 49, 77, 121, 203, 319, 413, 679, 721, 749, 841, 869, 1057; sie sind also recht häufig.

Zwar macht die Seltenheit der Perrinschen Pseudoprimzahlen die Perrin-Folge für Primzahltests interessant, der Rechenaufwand ist jedoch wesentlich höher (ca. 50 bis 100 mal) als für einen Miller-Rabin-Test. Mehrere Miller-Rabin-Tests mit mindestens 3 verschiedenen Basen ergeben eine geringere Anzahl von Pseudoprimzahlen bei deutlich geringerem Aufwand, und sind damit immer im Vorteil.

Häufigkeit und Überschneidung mit anderen Pseudoprimzahlen

[Bearbeiten]
Anzahl der Perrin-Pseudoprimzahlen im Vergleich
zu Primzahlen und Überschneidung mit fermatschen Pseudoprimzahlen
gleichzeitig Perrin &
Obergrenze x Primzahlen[4] spsp(2)[5] spsp(2, 13, 15) Perrin[5] f(x)(I) rPerrin psp(2) spsp(2) lpsp
106 78498 46 1 2 0,001 0 0 0 0
107 664579 162 1 2 0,001 0 0 0 0
108 5761455 488 1 7 0,054 2 1 1 0
109 50847534 1282 3 17 0,105 9 4 1 0
1010 455052511 3291 8 42 0,109 23 11 2 0
1011 4118054813 8607 22 116 0,111 71 32 11 0
1012 37607912018 22407 55 285 0,107 168 78 25 0
1013 346065536839 58892 164 649 0,112 375 193 69 0
1014 3204941750802 156251 459 1700 0,113 942 510 183 0

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

Quellen

[Bearbeiten]
  1.  Perrin-Folge
  2.  Perrin pseudoprimes
  3. OEIS:A018187
  4.  Primzahlsatz
  5. 5,0 5,1 Pseudoprime Statistics, Tables