Pseudoprimzahlen: Frobenius-Pseudoprimzahlen

Pseudoprimzahlen

Die Definition der Frobenius-Pseudoprimzahlen kann mit Lucas-Folgen $\ U_{n}(P,Q)\$ und $\ V_{n}(P,Q)$, wobei $D=P^{2}-4Q\$ keine Quadratzahl ist, wie folgt ausgedrückt werden.

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

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

(1)

$U_{n-\delta }(P,Q)\equiv 0{\pmod {n}}$ und

(2)

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

(3)

wobei $\delta =\left({\tfrac {D}{n}}\right)$ der Wert des Jacobi-Symbols ist.

Wenn Bedingung (2) erfüllt ist, ist Bedingung (3) äquivalent zu

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

(3')

.

Bezug zu anderen Pseudoprimzahlen

Jede Frobenius-Pseudoprimzahl $(P,Q)$ ist auch

• eine Lucas-Pseudoprimzahl mit den Parametern $(P,Q)$, da für diese die Bedingungen (1) and (2) gelten
• eine Dickson-Pseudoprimzahl mit den Parametern $(P,Q)$, da für diese die Bedingungen (1) and (3') gelten
• eine Fermatsche Pseudoprimzahl zur Basis $|Q|$, wenn $|Q|>1$.

Damit sind die Frobenius-Pseudoprimzahlen $(P,Q)$ eine echte Teilmenge der Lucas- and Dickson-Pseudoprimzahlen mit denselben Parametern $(P,Q)$ und der Fermatschen Pseudoprimzahlen zur Basis $|Q|$, wenn $|Q|>1$ ist.

Stärkere Kongruenzbedingung

In einem Primzahltest können statt Kongruenz 1 auch die Kongruenzbedingungen für starke Baillie-Wagstaff-Lucas-Pseudoprimzahlen angewandt werden, um den Test sicherer zu machen.

Da die Bezeichnung "starke Frobenius-Pseudoprimzahl" anderweitig vergeben ist, sollte sie hierfür nicht verwendet werden.

Frobenius-Fibonacci-Pseudoprimzahlen

Frobenius-Fibonacci-Pseudoprimzahlen sind Frobenius-Pseudoprimzahlen mit den Parametern P = 1 und Q = -1.

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

				gleichzeitig Frobenius(1,-1)- &
Obergrenze x	Frob(1,-1)	f(x)(I)	Frob(1,-1)sl	PsP(2)	sPsp(2)	lpsp	slpsp
10 3	0	-	0	0	0	0	0
10 4	3	0.002	2	0	0	1	1
10 5	16	0.033	14	0	0	3	3
10 6	56	0.041	41	7	2	11	11
10 7	210	0.032	142	34	7	38	38
10 8	653	0.030	399	90	22	105	105
10 9	1929	0.027	1165	255	50	304	304
1010	5241	0.024	3096	628	121	757	757
1011	14149	0.022	8165	1632	329	2034	2034
1012	37527	0.021	21354	3975	832	5339	5339
1013	98702	0.021	55909	9827	2247	14070	14070
1015					15952		101788

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

Frobenius(3,-5)-Pseudoprimzahlen

Die Häufigkeit von Frobenius-Pseudoprimzahlen kann abhängig von den Parametern sehr unterschiedlich sein. Mit den Parametern P = 3 und Q = -5 gibt es besonders wenige Pseudoprimzahlen. Die ersten sind 13333, 44801, 486157, 1615681, 3125281, 4219129, 9006401.

Anzahl der Frobenius(3,-5)-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen

				gleichzeitig Frobenius(3,-5)- &
Obergrenze x	Frob(3,-5)	f(x)(I)	Frob(3,-5)sl	PsP(2)	sPsp(2)	lpsp
10 3	0	-	0	0	0	0
10 4	0	-	0	0	0	0
10 5	2	0.109	1	0	0	0
10 6	3	0.084	1	0	0	0
10 7	7	0.088	4	3	2	0
10 8	27	0.092	8	10	6	0
10 9	82	0.108	30	29	8	0
1010	238	0.096	76	101	24	0
1011	604	0.097	201	258	60	0
1012	1532	0.098	550	676	171	0
1013	3897	0.101	1423	1644	409	0
1014					1032	0
1015					2864	0