Pseudoprimzahlen: Lehmer-Pseudoprimzahlen

Pseudoprimzahlen

Lehmer-Pseudoprimzahlen sind zusammengesetze natürliche Zahlen, die bestimmte Kriterien bezüglich der Lehmer-Folgen erfüllen, die von allen ungeraden Primzahlen erfüllt werden.

Lehmer-Folgen

Die Glieder der Lehmerfolgen werden im Folgenden mit $U_{k}(L,Q)$ und $V_{k}(L,Q)$ bezeichnet.
Sie sind wie folgt definiert:

• Anfangswerte:
  • $U_{0}=0,\quad U_{1}=1$
  • $V_{0}=2,\quad V_{1}=1$
• Rekursionsformeln für $k>1$:
  • $U_{k}={\begin{cases}L\cdot U_{k-1}-Q\cdot U_{k-2}&{\text{für ungerade }}k\\U_{k-1}-Q\cdot U_{k-2}&{\text{für gerade }}k\end{cases}}$
  • $V_{k}={\begin{cases}V_{k-1}-Q\cdot V_{k-2}&{\text{für ungerade }}k\\L\cdot V_{k-1}-Q\cdot V_{k-2}&{\text{für gerade }}k\end{cases}}$

Durch Beziehungen zwischen den Folgegliedern lassen sich diese auch für hohe Indizes, wie das z.B. für Primzahltests notwendig ist, effizient 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}{rclr}{\text{Diskriminante:}}\quad \quad \\D&=&L-4Q\\{\text{Berechnung}}\quad \quad \\X_{2k}{\text{ aus }}X_{k}{\text{: }}\quad \\U_{2k}&=&U_{k}V_{k}&\ &(a)\\V_{2k}&=&{\begin{cases}V_{k}^{2}-2Q^{k}&{\text{für gerade }}k&(b)\\LV_{k}^{2}-2Q^{k}&{\text{für ungerade }}k&(c)\end{cases}}&\\X_{k+1}{\text{ aus }}X_{k}{\text{: }}\quad \\V_{k+1}&=&{\frac {D\cdot U_{k}+V_{k}}{2}}&{\text{für gerade }}k&(d)\\U_{k+1}&=&{\frac {U_{k}+V_{k}}{2}}&{\text{für gerade }}k&(e)\\U_{k+1}&=&2\cdot QU_{k}+V_{k+1}&{\text{für gerade }}k&(f)\end{array}}$

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

Kongruenzen

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

1. $U_{n-\delta (n)}\equiv 0\$ mit $\ \delta (n)=\left({\tfrac {LD}{n}}\right)$
   • stark, mit $n-\delta (n)=d\cdot 2^{s}$:
     • $U_{d}\equiv 0\$ oder
     • $V_{d\cdot 2^{r}}\equiv 0\$ für ein $\ 0\leq r<s$
2. $V_{n-\delta (n)}\equiv 2\left({\tfrac {L}{n}}\right)Q^{(1-\delta (n))/2}$
3. $U_{n}\equiv \left({\tfrac {D}{n}}\right)$

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

Lehmer-Pseudoprimzahlen

Gegeben seien

• die ganzzahligen Parameter $L\$und $Q\$mit $\gcd(L,Q)=1$,
• die entsprechenden Lehmerfolgen $U_{k}(L,Q)$ und $V_{k}(L,Q)$,
• $D=L-4Q$,
• $n$ eine positive ganze Zahl und
• $\delta (n)=\left({\tfrac {D\cdot L}{n}}\right)$ der Wert des Jacobi-Symbols.

Mit jeder zu $LQD$ teilerfremden ungeraden Primzahl $n$ ist folgende Kongruenz erfüllt:

$U_{n-\delta (n)}\equiv 0{\pmod {n}}.$

(1)

Eine zusammengesetzte Zahl $n$ heißt Lehmer-Pseudoprimzahl, wenn diese Kongruenz erfüllt ist.

Euler-Lehmer-Pseudoprimzahlen

Eine ungerade zusammengesetzte Zahl ist eine Euler-Lehmer-Pseudoprimzahl, wenn $\gcd(n,QD)=1\$ und

$U_{\frac {n-\delta }{2}}\equiv 0{\pmod {n}}$, wenn $\left({\tfrac {QL}{n}}\right)=1\$ oder

$V_{\frac {n-\delta }{2}}\equiv 0{\pmod {n}}$, wenn $\left({\tfrac {QL}{n}}\right)=-1\$ ist.

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

$U_{n-\delta }=U_{\frac {n-\delta }{2}}\cdot V_{\frac {n-\delta }{2}}\equiv 0{\pmod {n}}$.

Daher sind Euler-Lehmer-Pseudoprimzahlen auch Lehmer-Pseudoprimzahlen mit den gleichen Parametern.

Starke Lehmer-Pseudoprimzahlen

Mit der Faktorisierung von $n-\delta (n)$ in $n-\delta (n)=d\cdot 2^{s}$ mit $d$ ungerade sind starke Lehmer-Pseudoprimzahlen zusammengesetze Zahlen mit $\gcd(n,2QD)=1\$, für die eine der Kongruenzen

$U_{d}\equiv 0{\pmod {n}}$

(1.1a)

oder

$V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}$ für ein $\ 0\leq r<s\$

(1.1b)

erfüllt ist.

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

Kongruenz 2

Für jede zu LQ teilerfremde ungerade Primzahl $n$ gilt auch

$V_{n-\delta }(L,Q)\equiv 2\left({\tfrac {L}{n}}\right)Q^{(1-\delta )/2}{\pmod {n}}$.

(2)

Pseudoprimzahlen, die diese Kongruenz erfüllen, sind seltener als solche, die Kongruenz 1 erfüllen.

Bis auf den Faktor $\left({\tfrac {L}{n}}\right)=\pm 1$ entspricht diese Kongruenz Bedingung 3 für Frobenius-Pseudoprimzahlen.

Pseudoprimzahlen, die sowohl Kongruenz 1 als auch Kongruenz 2 erfüllen, sind sehr selten.

Kongruenz 3

Wie oben angegeben, gilt für jede zu LQ teilerfremde ungerade Primzahl $n$ auch

$U_{n}\equiv \left({\tfrac {D}{n}}\right)$.

(3)

Pseudoprimzahlen, die diese Kongruenz erfüllen, sind seltener als solche, die Kongruenz 1 erfüllen.

Wenn $\left({\tfrac {D}{n}}\right)=0\$ist, haben $D$ und $n$ einen gemeinsamen Teiler; daher ist es zweckmäßig, Primzahltests auf Basis dieser Kongruenz abzubrechen, wenn das der Fall ist. Es gilt somit die zusätzliche Bedingung

$\gcd(2DLQ,n)=1$.

Lehmer-Pseudoprimzahlen mit n-abhängiger Parameterauswahl

Für Primzahltests haben sich experimentell Parameter mit $\left({\tfrac {D}{n}}\right)=-1$, $\left({\tfrac {LD}{n}}\right)=-1\$ und $|Q|>1\$ als besonders geeignet erwiesen, weil die Häufigkeit der Pseudoprimzahlen und die Überschneidung mit Fermatschen Pseudoprimzahlen damit gering sind. Dabei wird das kleinste D aus der Folge $D=3,7,11,...=4k+3\$ mit $k\geq 0$ und mit diesem das kleinste L aus der Folge $L=D+4\cdot Q$ mit $Q>1\$, so gewählt, dass die genannten Bedingungen erfüllt sind. Die Suche wird abgebrochen, wenn der Wert des Jacobi-Symbols Null ist, weil $n$ und $D$ bzw. $L$ dann einen gemeinsamen Teiler haben; wenn $n>D$ bzw. $n>L$ ist, was beim Test großer Zahlen gegeben ist, muss $n$ dann zusammengesetzt sein.

Die ersten derartigen Pseudoprimzahlen sind 377, 559, 1199, 1829, 2507, 2561, 2771, 3827, 4819, 4879, 5719, 5777, 7067, 7739, 9179; sieben davon sind starke Lehmer-Pseudoprimzahlen: 377, 559, 1199, 2507, 5719, 5777, 7067.

Die ersten Pseudoprimzahlen, die Kongruenz 2 (nicht aber 1) erfüllen, sind 108371, 42155801, 170067677.

Die ersten Pseudoprimzahlen, die Kongruenz 3 (nicht aber 1) erfüllen, sind 298574053, 1257360391, 3163076351, 4335829291.

Da die Bedingung $\left({\tfrac {LD}{n}}\right)=-1\$ größeren Einfluss als $\left({\tfrac {D}{n}}\right)=-1\$ hat, kann auch $L$ vorgegeben werden und das erste $D=L-4Q\$ mit $Q>1$, das diese Bedingung erfüllt, gesucht werden. Mit $L=-1$ gibt es dabei besonders wenige starke Lehmer-Pseudoprimzahlen.

Die ersten Pseudoprimzahlen mit dieser Parameterauswahl sind 527, 799, 1127, 1159, 1763, 2407, 2929, 3599, 4991, 5339, 5429, 6479, 6901, 8473; vier davon sind starke Lehmer-Pseudoprimzahlen: 799, 1127, 2407, 5429.

Die ersten Pseudoprimzahlen, die mit dieser Parameterauswahl Kongruenz 2 (nicht aber 1) erfüllen, sind 1121, 94669, 8788015.

Die ersten Pseudoprimzahlen, die mit dieser Parameterauswahl Kongruenz 3 (nicht aber 1) erfüllen, sind 264607, 592165, 2048801, 35626501, 37941077, 292524365, 502430627.

Häufigkeit

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

	$\left({\tfrac {D}{n}}\right)=-1$, $\left({\tfrac {LD}{n}}\right)=-1\$						gleichzeitig Lehmer- &
Obergrenze x	Lehmer	f(x)(I)	slehpsp	leh2psp	leh1&2psp	leh3psp	psp(2)	lpsp	slpsp	vlpsp(1, -1)
10 3	2	2,0·10-2	2	0	0	0	0	1	0	0
10 4	15	3,7·10-3	7	0	0	0	0	5	1	1
10 5	64	1,1·10-3	28	0	0	0	0	15	4	3
10 6	205	3,5·10-4	72	1	0	0	0	40	9	3
10 7	625	1,2·10-4	240	1	0	0	0	118	27	14
10 8	1666	4,5·10-5	569	2	0	0	0	284	71	38
10 9	4506	1,7·10-5	1477	3	0	1	0	792	215	123
1010	11876	6,4·10-6	3747	3	0	4	0	2037	555	326
1015							0	244330	71990	41365

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

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

	$L=-1$, $\left({\tfrac {LD}{n}}\right)=-1\$						gleichzeitig Lehmer(-1,*)- &
Obergrenze x	Lehmer(-1,*)	f(x)(I)	slehpsp	leh2psp	leh1&2psp	leh3psp	psp(2)	lpsp	slpsp	vlpsp(1, -1)
10 3	2	0	1	0	0	0	0	0	0	0
10 4	14	1,9·10-3	4	1	0	0	0	1	0	0
10 5	62	9,7·10-4	13	2	0	0	0	12	5	1
10 6	183	5,6·10-4	39	2	0	2	0	35	12	3
10 7	530	2,0·10-4	129	3	0	3	0	102	35	7
10 8	1528	6,8·10-5	356	3	0	5	0	255	77	14
10 9	4146	2,5·10-5	879	3	0	7	0	664	184	35
1010	10982	9,5·10-6	2351	3	0	10	0	1774	487	109
1015							0	208971	63654	15565