Pseudoprimzahlen: Lucas-Pseudoprimzahlen

Vorlage:Navigation Buch Lucas-Pseudoprimzahlen sind zusammengesetze natürliche Zahlen, die bestimmte Kriterien bezüglich der allgemeinen Lucas-Folgen erfüllen, die von allen ungeraden Primzahlen erfüllt werden.

Lucas-Folgen

Die Glieder der Lucasfolgen werden im Folgenden mit $U_k(P,Q)$ und $V_k(P,Q)$ bzw. $U_k$ und $V_k$ bezeichnet.
Sie sind wie folgt definiert:

• Anfangswerte:
  • $U_0=0,U_1=1$
  • $V_0=2,V_1=P$
• Rekursionsformeln für $k>1$:
  • $U_k=P\cdot U_{k-1}-Q\cdot U_{k-2}$
  • $V_k=P\cdot V_{k-1}-Q\cdot V_{k-2}$

Bezug zur quadratischen Gleichung

Die charakteristische Gleichung der Lucas-Folgen $U_k(P,Q)$ und $V_k(P,Q)$ ist

• $x^2-Px+Q=0$.

Sie hat die Diskriminante $D=P^2-4Q$ und die Wurzeln (Lösungen)

• $a=\frac{P+\sqrt{D}}{2}\text{und}b=\frac{P-\sqrt{D}}{2}$.

Daher ist:

• $a+b=P,$
• $ab=\frac{1}{4}(P^2-D)=Q,$
• $a-b=\sqrt{D}$.

Die Folgeglieder lassen sich mit den Wurzeln $a$ und $b$ wie folgt ausdrücken:

• $U_k=\frac{a^k-b^k}{a-b}$
• $V_k=a^k+b^k$

Diese Beziehungen sind allerdings für Primzahltests nur bedingt geeignet, weil $a,b,a^k$ und $b^k$ im Gegensatz zu $U_k$ und $V_k$ nicht ganzzahlig sind.

Beziehungen zwischen den Folgegliedern

Durch Beziehungen zwischen den Folgegliedern lassen sich diese auch für hohe Indizes, wie das z.B. für Primzahltests notwendig ist, effizient mit Ganzzahl-Arithmetik berechnen. Die Berechnung erfolgt dabei analog zum binären Potenzieren.

Die wichtigsten Beziehungen ($X_k$ steht dabei für $U_k$ bzw. $V_k$):

$\begin{array}{c}\text{Diskriminante:}\\ D& =& P^2-4Q\\ \text{Berechnung}\\ X_{2k}\text{ aus }{X}_k\text{: }\\ U_{2k}& =& U_k{V}_k& (a)\\ V_{2k}& =& V_k^2-2Q^k& (b)\\ X_{m+k}\text{ aus }{X}_m\text{ und }{X}_k\text{: }\\ U_{m+k}& =& \frac{U_m{V}_k+U_k{V}_m}{2}& (c)\\ V_{m+k}& =& \frac{V_m{V}_k+D\cdot U_m{U}_k}{2}& (d)\\ X_{k+1}\text{ aus }{X}_k\text{: }\\ U_{k+1}& =& \frac{P\cdot U_k+V_k}{2}& (e)\\ V_{k+1}& =& \frac{D\cdot U_k+P\cdot V_k}{2}& (f)\end{array}$

Zu $(c)\dots (f)$: Der Zähler ist immer gerade. Bei Berechnung Modulo $n$ können die Zwischenergebnisse Modulo $2n$ berechnet werden und das Endergebnis Modulo $n$.

Kongruenzen

Für jede ungerade, zu $Q$ teilerfremde Primzahl $n$gelten folgende Kongruenzen:

1. $U_{n-\delta (n)}\equiv 0$ mit $\delta (n)=\left(\frac{D}{n}\right)$
   • stark, mit $n-\delta (n)=d\cdot 2^s,2\nmid d$:
     • $U_d\equiv 0$ oder
     • $V_{d\cdot 2^r}\equiv 0$ für ein $0\le r<s$
2. $V_{n-\delta (n)}\equiv 2Q^{\frac{1-\delta (n)}{2}}=\{\begin{array}{cc}2Q,& \text{wenn }\delta (n)=-1\\ 2,& \text{wenn }\delta (n)=1\end{array}$
3. $U_n\equiv \left(\frac{D}{n}\right)$
4. $V_n\equiv P$

Dabei ist $\left(\frac{D}{n}\right)$ das Jacobi-Symbol.

Wenn $gcd(2DPQ,n)=1$ ist, d. h. $n$ ungerade und teilerfremd zu $D,P$ und $Q$ ist, folgen aus beliebigen zwei der genannten Kongruenzen die anderen beiden (bei Kongruenz 1 ohne die starke Kongruenzbedingung).

Lucas-Pseudoprimzahlen

Baillie und Wagstaff definieren Lucas-Pseudoprimzahlen wie folgt:

Gegeben seien

• die ganzzahligen Parameter $P>0$ und $Q$,
• die entsprechenden Lucasfolgen $U_k(P,Q)$ und $V_k(P,Q)$,
• $D=P^2-4Q$,
• $n$ eine positive ganze Zahl und
• $\delta (n)=\left(\frac{D}{n}\right)$ der Wert des Jacobi-Symbols.

Mit jeder zu $Q$ teilerfremden ungeraden Primzahl $n$ ist folgende Kongruenz erfüllt: Vorlage:Formel2 Eine zusammengesetzte Zahl $n$ heißt (Baillie-Wagstaff-) Lucas-Pseudoprimzahl, wenn diese Kongruenz erfüllt ist.

Kongruenz (1) ist eine der beiden Kongruenzen, die für Frobenius-Pseudoprimzahlen erfüllt sein müssen. Daher ist jede Frobenius-Pseudoprimzahl auch eine Lucas-Pseudoprimzahl.

Euler-Lucas-Pseudoprimzahlen

Eine ungerade zusammengesetzte Zahl ist eine Euler-Lucas-Pseudoprimzahl, wenn $gcd(n,QD)=1$ und Vorlage:Formel2 Vorlage:Formel2 Mit der Abhängigkeit der Kriterien vom Wert des Jacobi-Symbols besteht eine Analogie zu Euler-Jacobi-Pseudoprimzahlen und ohne diese Abhängigkeit zu Eulerschen Pseudoprimzahlen.

Aus $U_{2k}=U_k\cdot V_k$ folgt Vorlage:Formel2 Daher sind Euler-Lucas-Pseudoprimzahlen auch Lucas-Pseudoprimzahlen mit den gleichen Parametern.

Starke Lucas-Pseudoprimzahlen

Mit der Zerlegung von $n-\delta (n)$ in $n-\delta (n)=d\cdot 2^s$ mit $d$ ungerade sind starke Lucas-Pseudoprimzahlen zusammengesetze Zahlen, für die eine der Kongruenzen Vorlage:Formel2 oder Vorlage:Formel2 erfüllt ist.

Aus $U_{2k}=U_k\cdot V_k$ folgt, dass $U_{d\cdot 2^t}\equiv 0(\mathrm{mod}n)$ für alle $t>r$ ist.

Wenn jedoch $U_k\cdot V_k\equiv 0(\mathrm{mod}n)$ ist, und keiner der beiden Faktoren $(U_k,V_k)\equiv 0(\mathrm{mod}n)$ ist, hat $n$ mit beiden je einen gemeinsamen Teiler und kann keine Primzahl sein, ist aber Lucas-Pseudoprimzahl, jedoch keine starke. In diesem Fall sind $gcd(n,U_k)$ und $gcd(n,V_k)$ Teiler von $n$ (nicht unbedingt Primteiler).

Starke Lucas-Pseudoprimzahlen sind auch Euler-Lucas-Pseudoprimzahlen und Lucas-Pseudoprimzahlen mit den gleichen Parametern.

Umgekehrt ist jede Euler-Lucas-Pseudoprimzahl der Form $n-\delta (n)=4\cdot k+2$(also wenn $n-\delta (n)$ nicht durch 4 teilbar ist) starke Lucas-Pseudoprimzahl, da in diesen Fällen $s=1$ ist, und damit die Kriterien für Euler-Lucas-Pseudoprimzahlen denen für starke Lucas-Pseudoprimzahlen entsprechen.

Extrastarke Lucas-Pseudoprimzahlen

sind starke Lucas-Pseudoprimzahlen mit Parametersatz $(P,Q)$, wobei Q = 1 ist, die eine der Bedingungen Vorlage:Formel2 oder Vorlage:Formel2 erfüllen.

Extrastarke Lucas-Pseudoprimzahlen sind auch starke Lucas-Pseudoprimzahlen mit den gleichen Parametern $(P,Q)$.

Aus $V_d\equiv \pm 2(\mathrm{mod}n)$ folgt $V_{2d}=V_d^2-2Q\equiv 2(\mathrm{mod}n)$ und $V_{d\cdot 2^s}=V_{n+1}\equiv 2(\mathrm{mod}n)$.
Aus $V_{d\cdot 2^r}\equiv 0(\mathrm{mod}n)$ für ein$r<s-1$ folgt $V_{d\cdot 2^{r+1}}=V_{d\cdot 2^r}^2-2Q\equiv -2(\mathrm{mod}n)$ und daraus $V_{d\cdot 2^s}=V_{n+1}\equiv 2(\mathrm{mod}n)$.
Daher erfüllen alle extrastarken Lucas-Pseudoprimzahlen auch Kongruenz 2.

Von $n$ abhängige Parameterauswahl:
Es wird das kleinste $P\ge 3$ gewählt, mit dem $\left(\frac{D}{n}\right)=-1$ ist; dabei ist $D=P^2-4$, weil $Q=1$ ist. Die ersten extrastarken Lucas-Pseudoprimzahlen sind dann 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389, 73919, 75077.
Es sind keine Überschneidungen mit starken Pseudoprimzahlen zur Basis 2 bekannt.

Absolute Lucas-Pseudoprimzahlen

Eine absolute Lucas-Pseudoprimzahl zur Diskriminante D ist eine zusammengesetzte ganze Zahl $n$, die Kongruenz 1 mit allen Parameterpaaren (P, Q) mit der selben Diskriminante $D=P^2-4Q$ und $gcd(n,DQ)=1$ erfüllt.

Eine zusammengesetzte Zahl $n$ ist genau dann eine absolute Lucas-Pseudoprimzahl, wenn sie quadratfrei ist und für all ihre Primteiler ($p$) $p-\left(\frac{D}{p}\right)|n-\left(\frac{D}{n}\right)$ (Williams' Kriterium) gilt.

Beispiel: $323=17\cdot 19$ ist absolute Lucas-Pseudoprimzahl zur Diskriminante $D=5$;

• $17-\left(\frac{5}{17}\right)=18$,
• $19-\left(\frac{5}{19}\right)=18$,
• $323-\left(\frac{5}{323}\right)=324$,
• $18$ teilt $324$.

Parameterpaare mit $D=P^2-4Q=5$ sind zum Beispiel $(P,Q)=(1,-1),(3,1),(5,5)$.

Selfridge-Lucas-Pseudoprimzahlen

Ein Lucas-Primzahltest ist am nützlichsten, wenn $D$ so gewählt wird, dass der Wert des Jacobi-Symbols $\left(\frac{D}{n}\right)=-1$ ist.

John Selfridge hat dafür folgendes Parameterauswahlverfahren empfohlen:
Gewählt wird das erste $D$ aus $D=(2\cdot k+1)\cdot (-1{)}^k=5,-7,9,\mathrm{...}$mit $k>1$, das die Bedingung

$\left(\frac{D}{n}\right)=-1$

erfüllt, was voraussetzt, dass $n$ und $D$ teilerfremd sind.

Nachdem $D$ auf diese Weise bestimmt wurde, werden die Parameter $P=1$ und $Q=(1-D)/4$ gesetzt. Mit $\left(\frac{D}{n}\right)=-1$ ist $n-\delta (n)=n+1$ und $U_{n-\delta (n)}=U_{n+1}$.

Für jede Primzahl n gilt dann Kongruenz 1 mit $\delta (n)=-1$: Vorlage:Formel2 Zusammengesetzte Zahlen, für die diese Kongruenz erfüllt ist, sind Selfridge-Lucas-Pseudoprimzahlen.
Die ersten sind 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, 10877.

Anmerkungen:

Wenn $\left(\frac{D}{n}\right)=0$ ist, haben $n$ und $D$ einen gemeinsamen Teiler, und $n$ ist zusammengesetzt, wenn nicht $n=D=prim$ ist. Da das beschriebene Auswahlverfahren für Primzahltests vorgesehen ist, wird in solchen Fällen der Test abgebrochen. Deshalb gibt es auch keine durch 5 teilbaren Selfridge-Lucas-Pseudoprimzahlen.

Es wird nicht mit $D=-3$ begonnen, weil dann $P=Q=1$ und Kongruenz (1) mit allen ungeraden Zahlen erfüllt wäre.

Wenn $n$ eine Quadratzahl ist, gibt es kein $D$, mit dem obengenannte Bedingung erfüllt ist; dies sollte also vorher oder während des Auswahlverfahrens geprüft werden. Im Umkehrschluss bedeutet das auch, dass $n$ keine Quadratzahl ist, wenn ein $D$ gefunden wurde, das diese Bedingung erfüllt.

$\left(\frac{D}{n}\right)\ne -1$, wenn $D$ eine Quadratzahl ist, daher erfüllen Quadratzahlen die Bedingung nicht.

Alle Beträge von $D$, die größer als 15 sind, sind Primzahlen.

$|D|$ kann beliebig groß werden, z. B. größer als 100, wenn $n$ das Produkt aller Primzahlen unter 100 plus 1 ist; im Mittel führen aber weniger als 2 Versuche, ein geeignetes $D$ zu finden, zum Ziel.

Starke Selfridge-Lucas-Pseudoprimzahlen

Starke Selfridge-Lucas-Pseudoprimzahlen sind zusammengesetze Zahlen, für die eine der Bedingungen Vorlage:Formel2 oder Vorlage:Formel2 erfüllt ist.
Die ersten starken Selfridge-Lucas-Pseudoprimzahlen sind 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 58519.
Selfridge-Lucas-Pseudoprimzahlen gehören zu den wichtigsten Pseudoprimzahlen, weil der Selfridge-Lucas-Primzahltest Teil des Baillie-PSW-Primzahltests ist.

Selfridge-Frobenius-Pseudoprimzahlen

Kongruenz 1 ist eine der beiden Kongruenzbedingungen, die Frobenius-Pseudoprimzahlen erfüllen. Bei Auswahl der Parameter $(P,Q)$ wie oben, also mit $\left(\frac{D}{n}\right)=-1$, ist die zweite (Kongruenz 2) Vorlage:Formel2 Weniger als ein Viertel der starken Lucas-Pseudoprimzahlen mit gleichen Parametern erfüllt auch diese Kongruenz.

Die ersten derartigen Pseudoprimzahlen sind 5777, 10877, 75077, 100127, 113573.

Eigenschaften

Überschneidung mit starken Pseudoprimzahlen

Selfridge-Lucas-Pseudoprimzahlen sind selten auch Starke Pseudoprimzahlen; unter 10¹⁵ gibt es nur zwei starke Selfridge-Lucas-Pseudoprimzahlen, die auch starke Pseudoprimzahlen zu irgendeiner Basis unter 128 sind: 5777 (=76² + 1) zur Basis 76 und 104107121 zur Basis 104. Von den ersten 10 sind 4 zu keiner Basis zwischen 1 und n - 1 stark pseudoprim, die anderen 6 zu maximal 48 Basen (18971). Von den 474971 starken Selfridge-Lucas-Pseudoprimzahlen unter 10¹⁵ sind nur 154993 starke Pseudoprimzahlen zu irgendeiner Basis $a$ mit $a\ne 1unda\ne n-1$; das ist ein Anteil von ca. 33%, während der Anteil starker Pseudoprimzahlen an den ungeraden zusammengesetzten Zahlen im selben Bereich bei ca. 45% liegt.
Es wurde nachgewiesen, dass es unter 2⁶⁴ keine zusammengesetzen Zahlen gibt, die sowohl Selfridge-Lucas-Pseudoprimzahlen als auch starke Pseudoprimzahlen zur Basis 2 sind. Auch über dieser Grenze wurde noch keine solche Zahl gefunden.

Allerdings gibt es Parameter, mit denen starke Pseudoprimzahlen zur Basis 2 gleichzeitig starke Lucas-Pseudoprimzahlen sind, zum Beispiel ist 8321 starke Pseudoprimzahl zur Basis 2 und starke Lucas-Pseudoprimzahl mit den Parametern $P=92,Q=143$, $\left(\frac{D}{n}\right)=-1$ und erfüllt auch Kongruenz 2.

Teiler

Starke Selfridge-Lucas-Pseudoprimzahlen lassen sich häufig als Produkte der Form

$q=(2\cdot k\cdot x+1)\cdot (2\cdot m\cdot x-1)$ mit $x\in \mathbb{N}$,

$gcd(k,m)=1$und

$0<k\ll q,0<m\ll q$

ausdrücken. Umgekehrt ist der Anteil starker Selfridge-Lucas-Pseudoprimzahlen bei solchen Produkten deutlich höher als bei ungeraden Zahlen allgemein.

Häufigkeit

Lucas-Pseudoprimzahlen sind viel seltener als Primzahlen, wie folgende Tabelle zeigt.

Anzahl der Lucas-Pseudoprimzahlen im Vergleich
zu Primzahlen und fermatschen Pseudoprimzahlen

		Fermat		Selfridge-Lucas
Obergrenze x	Primzahlen	psp(2)	spsp(2)	lpsp	slpsp	vlpsp(1, -1)	vpsp	lpsp & psp(2)	slpsp: f(x)(I)
109	50.847.534	5.597	1.282	5.485	1.415	304	1	0	4,1·10-6
1012	37.607.912.018	101.629	22.407	116.928	25.542	5.339	3	0	2,3·10-7
1015	29.844.570.422.669	1.801.533	419.489	2.402.549	474.971	101.788	5	0	1,2·10-8

^(I) Vorlage:AnkerMittlerer Anteil falscher Zeugen beim Miller-Rabin-Test.

Restklassen

Starke Selfridge-Lucas-Pseudoprimzahlen liegen wesentlich häufiger in der Restklasse -1 modulo kleiner Zahlen $(m)$ als in anderen Restklassen. Folgende Tabelle zeigt die Verteilung der starken Selfridge-Lucas-Pseudoprimzahlen bis 10¹⁵ auf Restklassen modulo $m$ an ein paar Beispielen.

	Anzahl starker Selfridge-Lucas-Pseudoprimzahlen in Restklasse
m	0	1	2	3	4	5	6	7
3	656	78914	395401
5	0	81600	65141	36647	291583
7	15	55752	75056	33871	54977	41234	214066
8	0	74329	0	136178	0	73660	0	190804

Lucas-V-Pseudoprimzahlen

Wenn Selfridges Methode $D=5$ (und damit $Q=-1$) ergibt, können die Parameter so geändert werden, dass $P=Q=5$ ist; dabei bleibt $D$ unverändert. Für $D\ne 5$ bleiben $P$ und $Q$ unverändert.

Zusammengesetzte Zahlen, die mit diesem modifizierten Parameterauswahlverfahren Kongruenz 2 erfüllen, werden Lucas-V-Pseudoprimzahlen (vpsp) genannt. Diese sind sehr selten: bis 10¹⁵ gibt es nur 5:

913, 150267335403, 430558874533, 14760229232131 und 936916995253453; keine davon erfüllt auch Kongruenz 1 oder ist starke Pseudoprimzahl zu irgendeiner Basis unter 3,9⋅10¹⁰.

Falsche Zeugen bei Fermat- und Miller-Rabin-Test

	Fermat-Test, falsche Zeugen		Miller-Rabin-Test, falsche Zeugen
n	Anzahl	kleinster	Anzahl	kleinster
913	2	331	0	-
150267335403	30	6203146387	0	-
430558874533	142	1078176182	52	39764030759
14760229232131	34	310097526008	16	969257047267
936916995253453	46	1349585374882	4	62837152221620

Keine der Fermatschen Pseudoprimzahlen zur Basis 2 bis 2⁶⁴ ist auch Lucas-V-Pseudoprimzahl mit der obengenannten Parameterauswahl.

Pell-Pseudoprimzahlen

Mit den Parametern $P=2,Q=-1$ ist $U_n$ die Pell-Folge.
Für Pell-Pseudoprimzahlen gibt es drei alternative Definitionen, jeweils mit obengenannten Parametern:
Pell-Pseudoprimzahlen sind

a)	zusammengesetze Zahlen mit denen Kongruenz (1) erfüllt ist. Damit sind Pell-Pseudoprimzahlen also (Baillie-Wagstaff-) Lucas-Pseudoprimzahlen mit den Parametern P = 2 und Q = -1. Die ersten Pseudoprimzahlen sind dann 35, 169, 385, 779, 899, 961, 1121, 1189, 2419. Die ersten starken Pseudoprimzahlen mit diesen Parametern sind 169, 961, 1121, 3827, 6441, 6601, 7801, 8119.
b)	zusammengesetze Zahlen mit denen $U_n\equiv \left(\frac{2}{n}\right)(\mathrm{mod}n)$ erfüllt ist. Dies entspricht der obengenannten Kongruenz 3:$U_n\equiv \left(\frac{D}{n}\right)=\left(\frac{8}{n}\right)(\mathrm{mod}n)$. Auf Grund der Multiplikativität des Jacobi-Symbols gilt mit $D=8:\left(\frac{8}{n}\right)=\left(\frac{2^3}{n}\right)={\left(\frac{2}{n}\right)}^3=\left(\frac{2}{n}\right)\cdot {\left(\frac{2}{n}\right)}^2=\left(\frac{2}{n}\right)$. Die ersten Pseudoprimzahlen sind dann 169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215.
c)	ungerade zusammengesetze Zahlen mit denen $V_n(P,Q)\equiv P(\mathrm{mod}n)$ erfüllt ist. Pell-Pseudoprimzahlen nach dieser Definition sind damit Dickson-Pseudoprimzahlen mit den Parametern P = 2 und Q = -1 (D = 8). Die ersten Pseudoprimzahlen sind dann 169, 385, 961, 1105, 1121, 3827, 4901, 6265, 6441, 6601, 7107, 7801, 8119.

Da zur effizienten Berechnung von $U_n$ für große $n$ auch $V_n$ berechnet werden muss, können mit wenig Mehraufwand beide Bedingungen aus b) und c) geprüft werden. Die ersten Pseudoprimzahlen, die diese Bedingungen erfüllen, sind 169, 385, 961, 1121, 3827, 6265, 6441, 6601, 7801, 8119, 10945, 13067, 15841, 18241, 19097.

Häufigkeit

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

				gleichzeitig Pell &
Obergrenze x	Pell (b)	f(x)(I)	Pell (b&c)	PsP(2)	sPsP(2)	lpsp	slpsp	vlpsp(1, -1)
103	4	0.025	3	1	0	0	0	0
104	18	0.011	10	2	0	1	0	0
105	63	0.013	41	6	2	3	0	0
106	200	0.011	119	14	2	9	2	0
107	603	0.008	369	35	7	28	11	3
108	1722	0.007	1058	82	16	61	20	6
109	4851	0.006	2973	247	50	184	52	16
1010	12946	0.006	8064	666	139	485	126	46
1011	34265	0.006	21504	1638	328	1191	310	116
1012	89714	0.006	57083	4118	867	2916	777	287
1013	233541	0.006	149940	10404	2210	7272	2024	783