Pseudoprimzahlen: Bruckman-Lucas-Pseudoprimzahlen
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.
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
- für alle Primteiler von gilt, d. h. eine Carmichael-Zahl ist, und
- 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.
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.
Überschneidung mit Selfridge-Lucas-Pseudoprimzahlen
[Bearbeiten]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,0 1,1 Fibonacci pseudoprimes
- ↑ Pseudoprime Statistics, Tables
- ↑ en:Frobenius pseudoprime#Relations to other Pseudoprimes