Pseudoprimzahlen: Lucas-Pseudoprimzahlen zweiter Art

Für jede ungerade, zu $DQ$ teilerfremde Primzahl $n$ gilt folgende Kongruenz: Vorlage:Formel2 Dabei ist $\left(\frac{D}{n}\right)$ das Jacobi-Symbol.

Zusammengesetzte Zahlen, die diese Kongruenz erfüllen, heißen Lucas-Pseudoprimzahlen zweiter Art.

Lucas-Pseudoprimzahlen zweiter Art mit n-abhängigen Parametern

Die Anzahl der Pseudoprimzahlen und die Überschneidung mit Fermatschen Pseudoprimzahlen ist am geringsten, wenn die Parameter $P$ und $Q$ so gewählt werden, dass $\left(\frac{D}{n}\right)=-1$ ist.

P vorgegeben, Q variabel

Mit $P=7$ und dem kleinsten $D$ aus der Folge $D=(2\cdot k+1)\cdot (-1{)}^k=5,-7,9,\mathrm{...}$mit $k>1$, das obengenannte Bedingung erfüllt, sind die ersten Lucas-Pseudoprimzahlen zweiter Art 763, 271558981, 328773611, 27802367221, 98850994101.

Für Primzahltests sind Parameter mit $|Q|>1$ besser geeignet als solche mit $Q=\pm 1$, weil die Häufigkeit der Pseudoprimzahlen damit geringer ist. Daher ist es von Vorteil, wenn die Parameter in den Fällen mit $D=53\Rightarrow Q=-1$ in $P=5,Q=-7$ geändert werden, so dass $D$ unverändert bleibt. Die ersten Lucas-Pseudoprimzahlen zweiter Art sind auch mit dieser Parameterauswahl die oben genannten.

Da zur effizienten Berechnung von $U_n$ für große $n$ auch $V_n$ berechnet werden muss, kann mit wenig Mehraufwand auch die Kongruenz $V_n\equiv P$ geprüft werden; keine zusammengesetzte Zahl bis 10¹¹ erfüllt beide Kongruenzen mit $P=7$.

Die ersten Lucas-Pseudoprimzahlen zweiter Art mit $P=9$ sind 559, 1827, 39349, 305161, 1392371, 6560847, 12600151, 468473149, 867982219, 6925956511; keine davon erfüllt auch die Kongruenz $V_n\equiv P$. Bis 10¹¹ gibt es keine weitere derartige Pseudoprimzahl.

Überschneidung mit Fermatschen Pseudoprimzahlen

Mit Parametern, die mit dieser Methode bestimmt wurden, gibt es keine Überschneidung mit starken Pseudoprimzahlen zur Basis 2 unter 10¹⁹.

Von den Fermatschen Pseudoprimzahlen zur Basis 2 bis 2⁶⁴ sind folgende auch Lucas-Pseudoprimzahlen zweiter Art mit $P=7$: 7022077657287001, 244364175299216701, 14527843153864495181, 14888306940345489421, 16269659420262508261; davon ist nur 14527843153864495181 starke Pseudoprimzahl zur Basis 2.

Keine der Fermatschen Pseudoprimzahlen zur Basis 2 bis 2⁶⁴ ist Lucas-Pseudoprimzahl zweiter Art mit $P=9$ und dem oben beschriebenen Auswahlverfahren für $Q=(P^2-D)/4$.

Überschneidung mit Selfridge-Lucas-Pseudoprimzahlen

Nur eine der Selfridge-Lucas-Pseudoprimzahlen unter 10¹⁵ ist auch Lucas-Pseudoprimzahl zweiter Art mit der oben beschriebenen Parameterauswahl ohne die Modifikation bei $|Q|=1$: 470498037395299, in diesem Fall sind die Parameter $P=7,D=53\Rightarrow Q=-1$. Werden die Parameter in den Fällen mit $D=53$ in $P=5,Q=-7$ geändert, so dass $D$ unverändert bleibt, gibt es keine Überschneidungen mehr. Die ersten Lucas-Pseudoprimzahlen zweiter Art sind auch dann die oben genannten.