Pseudoprimzahlen: Fibonacci-Pseudoprimzahlen

Pseudoprimzahlen

Mit den Parametern $P=1$ und $Q=-1$ für die allgemeinen Lucas-Folgen ist $U_{k}(P,Q)$ die Fibonacci-Folge und $V_{k}(P,Q)$ die (spezielle) Lucas-Folge.

Fibonacci-Pseudoprimzahlen werden oft als zusammengesetze, nicht durch 5 teilbare Zahlen, für die

$U_{n-\delta }(P,Q)\equiv 0{\pmod {n}}\quad$ mit $\delta =\left({\tfrac {D}{n}}\right)$ (Jacobi-Symbol)

(1)

gilt, definiert. Die ersten Fibonacci-Pseudoprimzahlen nach dieser Definition sind 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877.

Da Kongruenz (1) auch die Bedingung für Baillie-Wagstaff-Lucas-Pseudoprimzahlen ist, sind Fibonacci-Pseudoprimzahlen nach dieser Definition auch Baillie-Wagstaff-Lucas-Pseudoprimzahlen mit den gleichen Parametern. Starke Baillie-Wagstaff-Lucas(1,-1)-Pseudoprimzahlen sind damit auch starke Fibonacci-Pseudoprimzahlen.

Häufigkeit und Überschneidung mit fermatschen und Lucas-Pseudoprimzahlen

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

				gleichzeitig Fibonacci- &
Obergrenze x	Fibonacci	f(x)(I)	starke Fibonacci	PsP(2)	sPsp(2)	lpsp	slpsp
10 3	2	0.005	0	0	0	2	0
10 4	9	0.038	2	1	0	4	1
10 5	50	0.028	14	4	0	24	3
10 6	155	0.030	41	15	3	69	11
10 7	511	0.024	142	50	9	192	38
10 8	1460	0.022	399	134	31	511	105
10 9	4152	0.019	1165	377	78	1380	304
1010	11049	0.018	3096	968	195	3509	757
1011	29334	0.017	8165	2517	525	9060	2034
1012	77188	0.016	21354	6222	1352	23235	5339
1013	202161	0.016	55908	15589	3653	60040	14070
1015					25829		101788

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

Bruckman-Lucas-Pseudoprimzahlen

Wenn $n$ eine Primzahl ist, gilt auch

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

(2)

Dies führt zu einer alternativen Definition der Fibonacci-Pseudoprimzahlen: Eine Fibonacci-Pseudoprimzahl ist eine zusammengesetze Zahl, mit der Kongruenz (2) erfüllt ist. Sie werden auch Bruckman-Lucas-Pseudoprimzahlen genannt. Die ersten derartigen Pseudoprimzahlen sind 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251.