Zum Inhalt springen

Pseudoprimzahlen: Bruckman-Lucas-Pseudoprimzahlen

Aus Wikibooks

Für jede Primzahl mit gilt

[1] (1)

wobei das n-te Glied der allgemeinen Lucas-Folge ist.


Definition

[Bearbeiten]

Eine Bruckman-Lucas-Pseudoprimzahl ist eine zusammengesetze Zahl, mit der Kongruenz (1) mit P = 1 und Q = -1 erfüllt ist; die ersten derartigen Pseudoprimzahlen sind dann 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251.

Verallgemeinerte Bruckman-Lucas-Pseudoprimzahlen sind zusammengesetzte Zahlen, die dieselbe Kongruenz mit beliebigen Parametern P und Q erfüllen.

Kongruenz (1) ist eine der Bedingungen für Dickson-Pseudoprimzahlen; letztere sind also auch Bruckman-Lucas-Pseudoprimzahlen mit den gleichen Parametern.

Anzahl der Bruckman-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen
gleichzeitig Bruckman(1,-1)- &
Obergrenze x Bruckman(1,-1)[2] f(x)(I) PsP(2) sPsp(2) lpsp slpsp
10 3 1 - 0 0 0 0
10 4 7 0.005 1 0 1 1
10 5 25 0.023 1 0 3 3
10 6 86 0.028 9 2 12 11
10 7 296 0.023 38 7 39 38
10 8 852 0.023 98 22 107 105
10 9 2365 0.022 270 50 306 304
1010 6285 0.020 655 121 759 757
1011 16554 0.019 1682 329 2036 2034
1012 43039 0.018 4073 835 5341 5339
1013 111443 0.018 9999 2255 14073 14070
1015 15970 101788

Absolute Bruckman-Lucas-Pseudoprimzahlen

[Bearbeiten]

Absolute Bruckman-Lucas-Pseudoprimzahlen sind zusammengesetzte Zahlen, die Kongruenz (1) mit und allen erfüllen. Das ist genau dann der Fall, wenn

  1. für alle Primteiler von gilt, d. h. eine Carmichael-Zahl ist, und
  2. oder für alle Primteiler von gilt.[1]

Die kleinste dieser Pseudoprimzahlen ist 443372888629441 = 17·31·41·43·89·97·167·331.

Diese Pseudoprimzahlen werden auch als "starke Fibonacci-Pseudoprimzahlen" bezeichnet, was aber irreführend ist, weil es keinen Primzahltest gibt, der solche Pseudoprimzahlen ohne Faktorisierung erkennen kann, etwa durch Prüfung einer stärkeren Kongruenzbedingung, wie zum Beispiel bei starken Lucas-Pseudoprimzahlen.

Dickson-Pseudoprimzahlen

[Bearbeiten]

Eine zusammengesetze Zahl n ist genau dann eine Dickson-Pseudoprimzahl, wenn

(d. h. n ist ungerade und teilerfremd zu Q und D), (2)

und

ist, (1)

wobei und die allgemeinen Lucas-Folgen sind.[3]

Wenn eine zusammengesetze Zahl n Bedingung (2) und die Kongruenz

, (3)

erfüllt, heißt sie Dickson-Pseudoprimzahl zweiter Art, wobei der Wert des Jacobi-Symbols ist.

Dickson-Fibonacci-Pseudoprimzahlen

[Bearbeiten]

Da Kongruenzbedingung (1) auch für Bruckman-Lucas-Pseudoprimzahlen gilt, sind Dickson-Pseudoprimzahlen mit auch Bruckman-Lucas-Pseudoprimzahlen mit den gleichen Parametern; der Unterschied liegt in Bedingung (2): Dickson-Pseudoprimzahlen (1, -1) sind nicht durch teilbar.

Anzahl der Dickson(1,-1)-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen
gleichzeitig Dickson(1,-1)- &
Obergrenze x Dickson(1,-1) f(x)(I) Dickson(2,-1) PsP(2) sPsp(2) lpsp slpsp
10 3 0 - 0 0 0 0 0
10 4 4 0.002 0 0 0 1 1
10 5 19 0.030 1 0 0 3 3
10 6 75 0.032 4 8 2 12 11
10 7 264 0.026 17 35 7 39 38
10 8 780 0.025 46 95 22 107 105
10 9 2193 0.023 117 264 50 306 304
1010 5875 0.021 268 644 121 759 757
1011 15642 0.020 630 1662 329 2036 2034
1012 40936 0.019 1592 4040 835 5341 5339
1013 106712 0.019 4069 9950 2253 14073 14070
1015 15966 101788

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

Dickson-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 5, -7, 9, -11, ..., das diese Bedingung erfüllt, sind die ersten Dickson-Pseudoprimzahlen 133, 713, 7097, 8113, 214613, 223721, 399001, 530881, 794139.

Nur eine der Selfridge-Lucas-Pseudoprimzahlen unter 1015 ist auch Dickson-Pseudoprimzahl mit der oben beschriebenen Parameterauswahl: 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 Dickson-Pseudoprimzahlen sind auch dann die oben genannten.

Quellen

[Bearbeiten]
  1. 1,0 1,1  Fibonacci pseudoprimes
  2. Pseudoprime Statistics, Tables
  3.  en:Frobenius pseudoprime#Relations to other Pseudoprimes