Zum Inhalt springen

Pseudoprimzahlen: Fibonacci-Pseudoprimzahlen

Aus Wikibooks

Mit den Parametern und für die allgemeinen Lucas-Folgen ist die Fibonacci-Folge und die (spezielle) Lucas-Folge.

Fibonacci-Pseudoprimzahlen werden oft als zusammengesetze, nicht durch 5 teilbare Zahlen, für die

mit (Jacobi-Symbol)[1] (1)

gilt, definiert. Die ersten Fibonacci-Pseudoprimzahlen nach dieser Definition sind 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877.

Da Kongruenz (1) auch die Bedingung für Baillie-Wagstaff-Lucas-Pseudoprimzahlen ist, sind Fibonacci-Pseudoprimzahlen nach dieser Definition auch Baillie-Wagstaff-Lucas-Pseudoprimzahlen mit den gleichen Parametern. Starke Baillie-Wagstaff-Lucas(1,-1)-Pseudoprimzahlen sind damit auch starke Fibonacci-Pseudoprimzahlen.


Häufigkeit und Überschneidung mit fermatschen und Lucas-Pseudoprimzahlen

[Bearbeiten]
Anzahl der Fibonacci-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen
gleichzeitig Fibonacci- &
Obergrenze x Fibonacci[2] f(x)(I) starke
Fibonacci
PsP(2) sPsp(2) lpsp slpsp
10 3 2 0.005 0 0 0 2 0
10 4 9 0.038 2 1 0 4 1
10 5 50 0.028 14 4 0 24 3
10 6 155 0.030 41 15 3 69 11
10 7 511 0.024 142 50 9 192 38
10 8 1460 0.022 399 134 31 511 105
10 9 4152 0.019 1165 377 78 1380 304
1010 11049 0.018 3096 968 195 3509 757
1011 29334 0.017 8165 2517 525 9060 2034
1012 77188 0.016 21354 6222 1352 23235 5339
1013 202161 0.016 55908 15589 3653 60040 14070
1015 25829 101788

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

Bruckman-Lucas-Pseudoprimzahlen

[Bearbeiten]

Wenn eine Primzahl ist, gilt auch

[1] (2)

Dies führt zu einer alternativen Definition der Fibonacci-Pseudoprimzahlen: Eine Fibonacci-Pseudoprimzahl ist eine zusammengesetze Zahl, mit der Kongruenz (2) erfüllt ist. Sie werden auch Bruckman-Lucas-Pseudoprimzahlen genannt. Die ersten derartigen Pseudoprimzahlen sind 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251.

Quellen

[Bearbeiten]
  1. 1,0 1,1  Fibonacci pseudoprimes
  2. Pseudoprime Statistics, Tables