Pseudoprimzahlen: Bruckman-Lucas-Pseudoprimzahlen

Pseudoprimzahlen

Für jede Primzahl $n$ mit $\gcd(n,Q)=1\$gilt

$V_{n}(P,Q)\equiv P{\pmod {n}},$

(1)

wobei $V_{n}(P,Q)$ das n-te Glied der allgemeinen Lucas-Folge ist.

Definition

Eine Bruckman-Lucas-Pseudoprimzahl ist eine zusammengesetze Zahl, mit der Kongruenz (1) mit P = 1 und Q = -1 erfüllt ist; die ersten derartigen Pseudoprimzahlen sind dann 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251.

Verallgemeinerte Bruckman-Lucas-Pseudoprimzahlen sind zusammengesetzte Zahlen, die dieselbe Kongruenz mit beliebigen Parametern P und Q erfüllen.

Kongruenz (1) ist eine der Bedingungen für Dickson-Pseudoprimzahlen; letztere sind also auch Bruckman-Lucas-Pseudoprimzahlen mit den gleichen Parametern.

Anzahl der Bruckman-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen

			gleichzeitig Bruckman(1,-1)- &
Obergrenze x	Bruckman(1,-1)	f(x)(I)	PsP(2)	sPsp(2)	lpsp	slpsp
10 3	1	-	0	0	0	0
10 4	7	0.005	1	0	1	1
10 5	25	0.023	1	0	3	3
10 6	86	0.028	9	2	12	11
10 7	296	0.023	38	7	39	38
10 8	852	0.023	98	22	107	105
10 9	2365	0.022	270	50	306	304
1010	6285	0.020	655	121	759	757
1011	16554	0.019	1682	329	2036	2034
1012	43039	0.018	4073	835	5341	5339
1013	111443	0.018	9999	2255	14073	14070
1015				15970		101788

Absolute Bruckman-Lucas-Pseudoprimzahlen

Absolute Bruckman-Lucas-Pseudoprimzahlen sind zusammengesetzte Zahlen, die Kongruenz (1) mit $Q=-1$ und allen $P$ erfüllen. Das ist genau dann der Fall, wenn

1. $p-1\mid n-1$ für alle Primteiler $p$ von $n$ gilt, d. h. $n$ eine Carmichael-Zahl ist, und
2. $2(p+1)\mid n-1\$oder $\ 2(p+1)\mid n-p$ für alle Primteiler $p$ von $n$ gilt.

Die kleinste dieser Pseudoprimzahlen ist 443372888629441 = 17·31·41·43·89·97·167·331.

Diese Pseudoprimzahlen werden auch als "starke Fibonacci-Pseudoprimzahlen" bezeichnet, was aber irreführend ist, weil es keinen Primzahltest gibt, der solche Pseudoprimzahlen ohne Faktorisierung erkennen kann, etwa durch Prüfung einer stärkeren Kongruenzbedingung, wie zum Beispiel bei starken Lucas-Pseudoprimzahlen.

Dickson-Pseudoprimzahlen

Eine zusammengesetze Zahl n ist genau dann eine Dickson-Pseudoprimzahl$(P,Q)$, wenn

$\gcd(n,2QD)=1\$ (d. h. n ist ungerade und teilerfremd zu Q und D),

(2)

und

$V_{n}(P,Q)\equiv P{\pmod {n}}\$ ist,

(1)

wobei $U_{n}(P,Q)$ und $V_{n}(P,Q)$ die allgemeinen Lucas-Folgen sind.

Wenn eine zusammengesetze Zahl n Bedingung (2) und die Kongruenz

$V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}}$,

(3)

erfüllt, heißt sie Dickson-Pseudoprimzahl$(P,Q)$ zweiter Art, wobei $\delta =\left({\tfrac {D}{n}}\right)$ der Wert des Jacobi-Symbols ist.

Dickson-Fibonacci-Pseudoprimzahlen

Da Kongruenzbedingung (1) auch für Bruckman-Lucas-Pseudoprimzahlen gilt, sind Dickson-Pseudoprimzahlen mit $P=1,Q=-1\$auch Bruckman-Lucas-Pseudoprimzahlen mit den gleichen Parametern; der Unterschied liegt in Bedingung (2): Dickson-Pseudoprimzahlen (1, -1) sind nicht durch $D=5\$teilbar.

Anzahl der Dickson(1,-1)-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen

			gleichzeitig Dickson(1,-1)- &
Obergrenze x	Dickson(1,-1)	f(x)(I)	Dickson(2,-1)	PsP(2)	sPsp(2)	lpsp	slpsp
10 3	0	-	0	0	0	0	0
10 4	4	0.002	0	0	0	1	1
10 5	19	0.030	1	0	0	3	3
10 6	75	0.032	4	8	2	12	11
10 7	264	0.026	17	35	7	39	38
10 8	780	0.025	46	95	22	107	105
10 9	2193	0.023	117	264	50	306	304
1010	5875	0.021	268	644	121	759	757
1011	15642	0.020	630	1662	329	2036	2034
1012	40936	0.019	1592	4040	835	5341	5339
1013	106712	0.019	4069	9950	2253	14073	14070
1015					15966		101788

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

Dickson-Pseudoprimzahlen mit n-abhängigen Parametern

Die Anzahl der Pseudoprimzahlen und die Überschneidung mit Fermatschen Pseudoprimzahlen ist am geringsten, wenn die Parameter $P$ und $Q$ so gewählt werden, dass $\left({\tfrac {D}{n}}\right)=-1$ ist.

Mit $P=7$ und dem kleinsten $D$ aus der Folge 5, -7, 9, -11, ..., das diese Bedingung erfüllt, sind die ersten Dickson-Pseudoprimzahlen 133, 713, 7097, 8113, 214613, 223721, 399001, 530881, 794139.

Überschneidung mit Selfridge-Lucas-Pseudoprimzahlen

Nur eine der Selfridge-Lucas-Pseudoprimzahlen unter 10¹⁵ ist auch Dickson-Pseudoprimzahl mit der oben beschriebenen Parameterauswahl: 470498037395299, in diesem Fall sind die Parameter $P=7,D=53\Rightarrow Q=-1$. Werden die Parameter in den Fällen mit $D=53\$ in $\ P=5,Q=7$ geändert, so dass $D$ unverändert bleibt, gibt es keine Überschneidungen mehr. Die ersten Dickson-Pseudoprimzahlen sind auch dann die oben genannten.