Pseudoprimzahlen: Lucas3-Pseudoprimzahlen
Für jede ungerade, zu teilerfremde Primzahl gilt folgende Kongruenz:
mit . | (1) |
Dabei ist das Jacobi-Symbol.
Zusammengesetzte Zahlen, die diese Kongruenz mit den Parametern erfüllen, heißen Pell-Pseudoprimzahlen ( 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 Bearbeiten
Die Anzahl der Pseudoprimzahlen und die Überschneidung mit Fermatschen Pseudoprimzahlen ist am geringsten, wenn die Parameter und so gewählt werden, dass ist.
Mit und dem kleinsten aus der Folge mit , das diese Bedingung erfüllt, sind die ersten Lucas3-Pseudoprimzahlen 763, 271558981, 328773611, 27802367221, 98850994101.
Für Primzahltests sind Parameter mit besser geeignet als solche mit , weil die Häufigkeit der Pseudoprimzahlen damit geringer ist. Daher ist es von Vorteil, wenn die Parameter in den Fällen mit in geändert werden, so dass unverändert bleibt. Die ersten Lucas3-Pseudoprimzahlen sind auch mit dieser Parameterauswahl die oben genannten.
Da zur effizienten Berechnung von für große auch berechnet werden muss, kann mit wenig Mehraufwand auch die Kongruenz geprüft werden; keine zusammengesetze Zahl bis 1011 erfüllt beide Kongruenzen mit .
Überschneidung mit Fermatschen Pseudoprimzahlen Bearbeiten
Mit Parametern, die mit dieser Methode bestimmt wurden, gibt es keine Überschneidung mit starken Pseudoprimzahlen zur Basis 2 unter 1019.
Von den Fermatschen Pseudoprimzahlen zur Basis 2 bis 264 sind folgende auch Lucas3-Pseudoprimzahlen mit : 7022077657287001, 244364175299216701, 14527843153864495181, 14888306940345489421, 16269659420262508261; davon ist nur 14527843153864495181 starke Pseudoprimzahl zur Basis 2.
Überschneidung mit Selfridge-Lucas-Pseudoprimzahlen Bearbeiten
Nur eine der Selfridge-Lucas-Pseudoprimzahlen unter 1015 ist auch Lucas3-Pseudoprimzahl mit der oben beschriebenen Parameterauswahl ohne die Modifikation bei : 470498037395299, in diesem Fall sind die Parameter . Werden die Parameter in den Fällen mit in geändert, so dass unverändert bleibt, gibt es keine Überschneidungen mehr. Die ersten Lucas3-Pseudoprimzahlen sind auch dann die oben genannten.