Pseudoprimzahlen: Perrinsche Pseudoprimzahlen

Pseudoprimzahlen

Die Perrin-Folge $P(k)$ 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).

Perrinsche Pseudoprimzahlen sind zusammengesetzte Zahlen $n$, die $P(n)$ teilen.

Perrin-Folge

Die Glieder der Perrin-Folge sind wie folgt definiert:
${\begin{array}{l}\quad P_{0}=3\\\quad P_{1}=0\\\quad P_{2}=2\\\quad P_{k}=P_{k-2}+P_{k-3}\end{array}}$

Aus obiger Bildungsregel folgt
$\ \quad P_{k}=P_{k+3}-P_{k+1}$;

damit kann die Folge auf negative Indizes $k<0$ erweitert werden.

Matrixformel

Beliebige Folgeglieder können mit der Matrixformel

${\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{\!k}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P\left(k\right)\\P\left(k+1\right)\\P\left(k+2\right)\end{pmatrix}}$

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:

${\begin{pmatrix}-1&0&1\\1&0&0\\0&1&0\end{pmatrix}}^{\!k}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P\left(-k\right)\\P\left(-k+1\right)\\P\left(-k+2\right)\end{pmatrix}}$

Perrin-Pseudoprimzahlen

Alle Primzahlen $n$ teilen $P(n)$:

$P(n)\equiv 0{\pmod {n}}$.

(1)

Es gibt aber auch zusammengesetzte Zahlen $n$, die $P(n)$ teilen; diese werden Perrinsche Pseudoprimzahlen genannt. 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

$P(-n)\equiv -1{\pmod {n}}$.

(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.

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

Anzahl der Perrin-Pseudoprimzahlen im Vergleich
zu Primzahlen und Überschneidung mit fermatschen Pseudoprimzahlen

							gleichzeitig Perrin &
Obergrenze x	Primzahlen	spsp(2)	spsp(2, 13, 15)	Perrin	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.