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.

Die Häufigkeit kann durch Prüfung der Kongruenzen für starke Lucas-Pseudoprimzahlen noch weiter reduziert werden. Damit sind die ersten Pseudoprimzahlen mit diesen Parametern 44801, 3125281, 4219129, 9006401.

Mit wenig Mehraufwand können auch die Kongruenzen für starke Pseudoprimzahlen zur Basis $Q=5$ geprüft werden; dadurch wird die Häufigkeit weiter reduziert. Die ersten starken Lucas-Pseudoprimzahlen, die auch diese Kongruenzen erfüllen sind 44801, 4219129, 9006401, 25052527, 26332181, 51733921, 67194401.

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	Frob(3,-5)sl und sPsP(5)	sPsP(5)	PsP(2)	sPsp(2)	lpsp
10 3	0	-	0	0	0	0	0	0
10 4	0	-	0	0	0	0	0	0
10 5	2	0.109	1	1	1	0	0	0
10 6	3	0.084	1	1	1	0	0	0
10 7	7	0.088	4	3	3	3	2	0
10 8	27	0.092	8	7	8	10	6	0
10 9	82	0.108	30	28	32	29	8	0
1010	238	0.096	76	70	76	101	24	0
1011	604	0.097	201	173	188	258	60	0
1012	1532	0.098	550	474	539	676	171	0
1013	3897	0.101	1423	1255	1421	1644	409	0
1014							1032	0
1015							2864	0