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(\mathrm{mod}n)$ und

(2)

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

(3)

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

Aus den Bedingungen (1), (2) und (3) folgt, dass auch die Kongruenzen

$U_n\equiv \left(\frac{D}{n}\right)$ und

(4)

$V_n(P,Q)\equiv P(\mathrm{mod}n)$.

(5)

erfüllt sind.

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) und (2) gelten.
• eine Lucas-Pseudoprimzahl zweiter Art mit den Parametern $(P,Q)$, da für diese die Bedingungen (1) und (4) gelten.
• eine Dickson-Pseudoprimzahl mit den Parametern $(P,Q)$, da für diese die Bedingungen (1) und (5) gelten.
• eine Dickson-Pseudoprimzahl zweiter Art mit den Parametern $(P,Q)$, da für diese die Bedingungen (1) und (3) gelten.
• eine Fermatsche Pseudoprimzahl zur Basis $|Q|$, wenn $|Q|>1$.

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

Extrastarke Lucas-Pseudoprimzahlen

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

Die Kongruenzbedingungen sind damit die gleichen wie für die im Kapitel Lucas-Pseudoprimzahlen beschriebenen extrastarken Lucas-Pseudoprimzahlen, nur mit den (allgemeinen) Parametern $(P,Q)$.

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)	eslpsp(1,-1)	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)	eslpsp(3,-5)	eslpsp(3,-5) 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

Frobenius(1,15)-Pseudoprimzahlen

Allgemein sind Frobenius-Pseudoprimzahlen mit $|Q|\ne 1$ viel seltener als solche mit $Q=\pm 1$. Mit $P=1,Q=15$ sind sie noch etwas seltener als mit $P=3,Q=-5$:

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

					gleichzeitig Frobenius(1,15)- &
Obergrenze	Frob(1,15)	f(x)(I)	eslpsp(1,15)	eslpsp(1,15) und sPsP(15)	sPsP(15)	PsP(2)	sPsp(2)	lpsp
10 3	0	0.000	0	0	0	0	0	0
10 4	0	0.000	0	0	0	0	0	0
10 5	0	0.000	0	0	0	0	0	0
10 6	1	0.249	0	0	0	0	0	0
10 7	11	0.132	6	4	4	6	2	0
10 8	19	0.110	6	4	4	12	2	0
10 9	71	0.095	19	14	18	42	4	0
1010	212	0.090	61	48	60	105	21	0
1011	521	0.094	161	136	162	275	61	0
1012	1302	0.098	413	359	411	606	133	0
1013	3461	0.101	1125	991	1115	1529	359	0
1014	8988	0.105	3124	2766	3102	3723	944	0
1015						9308	2640	0

Die ersten derartigen Pseudoprimzahlen sind

• 218791, 1024651, 2508013, 4128703, 4224533, 5148001, 5444489, 7519441, 8095447 ohne Erfüllung weiterer Bedingungen,
• 1024651, 4128703, 4224533, 5148001, 7519441, 8595361, 114329881, 165283471, 180115489 mit der Kongruenz starker Lucas-Pseudoprimzahlen
• und 1024651, 4128703, 4224533, 8595361, 165283471, 201261061, 253158751, 300484549, 311076001 zusätzlich mit der Kongruenz starker Pseudoprimzahlen.

Frobenius-Pseudoprimzahlen mit n-abhängigen Parametern

Die Häufigkeit von Frobenius-Pseudoprimzahlen ist am geringsten, wenn die Parameter $P$ und $Q$ so gewählt werden, dass $\left(\frac{D}{n}\right)=-1$ ist.

Bei allen Frobenius-Pseudoprimzahlen bis $3\cdot 10^{13}$ mit den Parametern $P=3,Q=-5$ ist $\left(\frac{P^2-4Q}{n}\right)=\left(\frac{D}{n}\right)=1$.

Bis $3\cdot 10^{13}$ gibt es keine Frobenius-Pseudoprimzahlen mit $Q=-5$, wenn für $P$ die kleinste ungerade Zahl gewählt wird, mit der $\left(\frac{D}{n}\right)=-1$ ist. Darüberhinaus sind keine bekannt.

Bei allen Frobenius-Pseudoprimzahlen bis $10^{14}$ mit den Parametern $P=1,Q=15$ ist $\left(\frac{P^2-4Q}{n}\right)=\left(\frac{D}{n}\right)=1$.

Bis $10^{14}$ gibt es keine Frobenius-Pseudoprimzahlen mit $Q=15$, wenn für $P$ die kleinste ungerade Zahl gewählt wird, mit der $\left(\frac{D}{n}\right)=-1$ ist. Darüberhinaus sind keine bekannt.