Pseudoprimzahlen: Lucas3-Pseudoprimzahlen

Pseudoprimzahlen

Für jede ungerade, zu $DQ$ teilerfremde Primzahl $n$ gilt folgende Kongruenz:

$U_{n}(P,Q)\equiv \left({\tfrac {D}{n}}\right)\$ mit $\ D=P^{2}-4Q$.

(1)

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

Zusammengesetzte Zahlen, die diese Kongruenz mit den Parametern $\ P=2,\ Q=-1\$ erfüllen, heißen Pell-Pseudoprimzahlen ($U_{n}(2,-1)$ ist die Pell-Folge). Für Pseudoprimzahlen, die dieselbe Kongruenz mit anderen Parametern erfüllen, gibt es keinen speziellen Namen; daher werden sie hier Lucas3-Pseudoprimzahlen genannt.

Lucas3-Pseudoprimzahlen 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({\tfrac {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,...\$mit $k>1$, das obengenannte Bedingung erfüllt, sind die ersten Lucas3-Pseudoprimzahlen 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 Lucas3-Pseudoprimzahlen 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 Lucas3-Pseudoprimzahlen 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 Lucas3-Pseudoprimzahlen 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 Lucas3-Pseudoprimzahl 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 Lucas3-Pseudoprimzahl 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 Lucas3-Pseudoprimzahlen sind auch dann die oben genannten.