Zum Inhalt springen

Pseudoprimzahlen: Lehmer-Pseudoprimzahlen

Aus Wikibooks

Lehmer-Pseudoprimzahlen sind zusammengesetze natürliche Zahlen, die bestimmte Kriterien bezüglich der Lehmer-Folgen erfüllen, die von allen ungeraden Primzahlen erfüllt werden.

Lehmer-Folgen

[Bearbeiten]

Die Glieder der Lehmerfolgen werden im Folgenden mit und bezeichnet.
Sie sind wie folgt definiert:

  • Anfangswerte:
  • Rekursionsformeln für :[1]


Durch Beziehungen zwischen den Folgegliedern lassen sich diese auch für hohe Indizes, wie das z.B. für Primzahltests notwendig ist, effizient berechnen. Die Berechnung erfolgt dabei analog zum binären Potenzieren.

Die wichtigsten Beziehungen ( steht dabei für bzw. ):


Zu : Der Zähler ist immer gerade. Bei Berechnung Modulo können die Zwischenergebnisse Modulo berechnet werden und ganz zum Schluss das Endergebnis Modulo .

Kongruenzen

[Bearbeiten]

Für jede ungerade, zu teilerfremde Primzahl gelten folgende Kongruenzen:[2]

  1. mit
    • stark, mit :
      • oder
      • für ein

Dabei ist das Jacobi-Symbol.

Lehmer-Pseudoprimzahlen

[Bearbeiten]

Gegeben seien

  • die ganzzahligen Parameter und mit ,
  • die entsprechenden Lehmerfolgen und ,
  • ,
  • eine positive ganze Zahl und
  • der Wert des Jacobi-Symbols.

Mit jeder zu teilerfremden ungeraden Primzahl ist folgende Kongruenz erfüllt:

(1)

Eine zusammengesetzte Zahl heißt Lehmer-Pseudoprimzahl, wenn diese Kongruenz erfüllt ist.

Euler-Lehmer-Pseudoprimzahlen

[Bearbeiten]

Eine ungerade zusammengesetzte Zahl ist eine Euler-Lehmer-Pseudoprimzahl, wenn und

, wenn oder  
, wenn ist.[1]  

Mit der Abhängigkeit der Kriterien vom Wert des Jacobi-Symbols besteht eine Analogie zu Euler-Jacobi-Pseudoprimzahlen und ohne diese Abhängigkeit zu Eulerschen Pseudoprimzahlen.

Aus folgt

.  

Daher sind Euler-Lehmer-Pseudoprimzahlen auch Lehmer-Pseudoprimzahlen mit den gleichen Parametern.

Starke Lehmer-Pseudoprimzahlen

[Bearbeiten]

Mit der Faktorisierung von in mit ungerade sind starke Lehmer-Pseudoprimzahlen zusammengesetze Zahlen mit , für die eine der Kongruenzen

(1.1a)

oder

für ein (1.1b)

erfüllt ist.

Starke Lehmer-Pseudoprimzahlen sind auch Euler-Lehmer-Pseudoprimzahlen und Lehmer-Pseudoprimzahlen mit den gleichen Parametern.

Kongruenz 2

[Bearbeiten]

Für jede zu LQ teilerfremde ungerade Primzahl gilt auch

.[2] (2)

Pseudoprimzahlen, die diese Kongruenz erfüllen, sind seltener als solche, die Kongruenz 1 erfüllen.

Bis auf den Faktor entspricht diese Kongruenz Bedingung 3 für Frobenius-Pseudoprimzahlen.

Pseudoprimzahlen, die sowohl Kongruenz 1 als auch Kongruenz 2 erfüllen, sind sehr selten.

Kongruenz 3

[Bearbeiten]

Wie oben angegeben, gilt für jede zu LQ teilerfremde ungerade Primzahl auch

.[2] (3)

Pseudoprimzahlen, die diese Kongruenz erfüllen, sind seltener als solche, die Kongruenz 1 erfüllen.

Wenn ist, haben und einen gemeinsamen Teiler; daher ist es zweckmäßig, Primzahltests auf Basis dieser Kongruenz abzubrechen, wenn das der Fall ist. Es gilt somit die zusätzliche Bedingung

.  

Lehmer-Pseudoprimzahlen mit n-abhängiger Parameterauswahl

[Bearbeiten]

Für Primzahltests haben sich experimentell Parameter mit , und als besonders geeignet erwiesen, weil die Häufigkeit der Pseudoprimzahlen und die Überschneidung mit Fermatschen Pseudoprimzahlen damit gering sind. Dabei wird das kleinste D aus der Folge mit und mit diesem das kleinste L aus der Folge mit , so gewählt, dass die genannten Bedingungen erfüllt sind. Die Suche wird abgebrochen, wenn der Wert des Jacobi-Symbols Null ist, weil und bzw. dann einen gemeinsamen Teiler haben; wenn bzw. ist, was beim Test großer Zahlen gegeben ist, muss dann zusammengesetzt sein.[2]

Die ersten derartigen Pseudoprimzahlen sind 377, 559, 1199, 1829, 2507, 2561, 2771, 3827, 4819, 4879, 5719, 5777, 7067, 7739, 9179; sieben davon sind starke Lehmer-Pseudoprimzahlen: 377, 559, 1199, 2507, 5719, 5777, 7067.

Die ersten Pseudoprimzahlen, die Kongruenz 2 (nicht aber 1) erfüllen, sind 108371, 42155801, 170067677.

Die ersten Pseudoprimzahlen, die Kongruenz 3 (nicht aber 1) erfüllen, sind 298574053, 1257360391, 3163076351, 4335829291.


Da die Bedingung größeren Einfluss als hat, kann auch vorgegeben werden und das erste mit , das diese Bedingung erfüllt, gesucht werden. Mit gibt es dabei besonders wenige starke Lehmer-Pseudoprimzahlen.

Die ersten Pseudoprimzahlen mit dieser Parameterauswahl sind 527, 799, 1127, 1159, 1763, 2407, 2929, 3599, 4991, 5339, 5429, 6479, 6901, 8473; vier davon sind starke Lehmer-Pseudoprimzahlen: 799, 1127, 2407, 5429.

Die ersten Pseudoprimzahlen, die mit dieser Parameterauswahl Kongruenz 2 (nicht aber 1) erfüllen, sind 1121, 94669, 8788015.

Die ersten Pseudoprimzahlen, die mit dieser Parameterauswahl Kongruenz 3 (nicht aber 1) erfüllen, sind 264607, 592165, 2048801, 35626501, 37941077, 292524365, 502430627.


Häufigkeit

[Bearbeiten]
Anzahl der Lehmer-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen
, gleichzeitig Lehmer- &
Obergrenze x Lehmer f(x)(I) slehpsp leh2psp leh1&2psp leh3psp psp(2) lpsp slpsp vlpsp(1, -1)
10 3 2 2,0·10-2 2 0 0 0 0 1 0 0
10 4 15 3,7·10-3 7 0 0 0 0 5 1 1
10 5 64 1,1·10-3 28 0 0 0 0 15 4 3
10 6 205 3,5·10-4 72 1 0 0 0 40 9 3
10 7 625 1,2·10-4 240 1 0 0 0 118 27 14
10 8 1666 4,5·10-5 569 2 0 0 0 284 71 38
10 9 4506 1,7·10-5 1477 3 0 1 0 792 215 123
1010 11876 6,4·10-6 3747 3 0 4 0 2037 555 326
1015 0 244330 71990 41365

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

Anzahl der Lehmer(-1,*)-Pseudoprimzahlen und Überschneidung
mit fermatschen und Lucas-Pseudoprimzahlen
, gleichzeitig Lehmer(-1,*)- &
Obergrenze x Lehmer(-1,*) f(x)(I) slehpsp leh2psp leh1&2psp leh3psp psp(2) lpsp slpsp vlpsp(1, -1)
10 3 2 0 1 0 0 0 0 0 0 0
10 4 14 1,9·10-3 4 1 0 0 0 1 0 0
10 5 62 9,7·10-4 13 2 0 0 0 12 5 1
10 6 183 5,6·10-4 39 2 0 2 0 35 12 3
10 7 530 2,0·10-4 129 3 0 3 0 102 35 7
10 8 1528 6,8·10-5 356 3 0 5 0 255 77 14
10 9 4146 2,5·10-5 879 3 0 7 0 664 184 35
1010 10982 9,5·10-6 2351 3 0 10 0 1774 487 109
1015 0 208971 63654 15565

Quellen

[Bearbeiten]
  1. 1,0 1,1 On Euler Lehmer Pseudoprimes and Strong Lehmer Pseudoprimes ... A. Rotkiewicz
  2. 2,0 2,1 2,2 2,3 Extensions in the theory of Lucas and Lehmer pseudoprimes - Washington State University, Andrew David Loveless