Pseudoprimzahlen: Starke Pseudoprimzahlen

Jede ungerade Primzahl erfüllt mit jeder teilerfremden ganzzahligen Basis eine der Kongruenzen

mit und ungerade (1)
für ein mit (2)

. Anmerkung: Kongruenz (2) ist gleichbedeutend mit .


Definition

Bearbeiten

Eine ungerade Zahl   ist starke Pseudoprimzahl zur Basis  , wenn sie zusammengesetzt ist, und mit einer ganzzahligen Basis  , für die   gilt, eine der obengenannten Kongruenzen erfüllt ist. In dieser Hinsicht verhält sie sich wie eine Primzahl.

Die obengenannten Kongruenzen werden im Miller-Rabin-Test[1] genutzt, um zu prüfen ob eine ungerade Zahl (wahrscheinlich) eine Primzahl oder sicher keine ist; dabei kann durch Tests mit mehreren Basen die Wahrscheinlichkeit, dass eine Pseudoprimzahl den Test besteht, reduziert werden.

Eigenschaften

Bearbeiten

Im Gegensatz zu den Fermatschen Pseudoprimzahlen gibt es keine starken Pseudoprimzahlen, die zu jeder teilerfremden Basis pseudoprim sind; eine Entsprechung zu den Carmichael-Zahlen gibt es also nicht.

Alle zusammengesetzten Mersennezahlen (  mit   = prim) sind starke Pseudoprimzahlen zur Basis 2.

Alle zusammengesetzten Fermatzahlen ( ) sind starke Pseudoprimzahlen zur Basis 2.[2]

  ist starke Pseudoprimzahl zur Basis 2, wenn   und eine Primzahl ist.[3]

Die Quadrate der Wieferich-Primzahlen sind starke Pseudoprimzahlen zur Basis 2.

Bezug zu Eulerschen Pseudoprimzahlen

Bearbeiten

Jede starke Pseudoprimzahl   zur Basis   ist auch eine Eulersche Pseudoprimzahl zur Basis  .
Warum? Für eine eulersche Pseudoprimzahl zur Basis   gilt  .

  lässt sich auch als   schreiben. Wenn nun   gilt, gilt auch   und damit auch  .


Jede eulersche Pseudoprimzahl der Form   ist starke Pseudoprimzahl:
in diesem Fall ist   und   und damit  ; mit   ist also eine der obengenannten Kongruenzen erfüllt.


Für alle Primteiler   einer starken Pseudoprimzahl  gilt

  •   und damit
  •  ,

wobei   die multiplikative Ordnung von   zur Basis   ist.[4] [5][6]

Die höchste Zweierpotenz, durch die die multiplikative Ordnung eines Primteilers teilbar ist, ist für alle Teiler einer starken Pseudoprimzahl gleich, d. h. alle multiplikativen Ordnungen der Primteiler derselben starken Pseudoprimzahl sind Produkt einer ungeraden Zahl und derselben Zweierpotenz (einschließlich  ).[7]

Starke Pseudoprimzahlen sind weitgehend quadratfrei; nur die Quadrate der Wieferich-Primzahlen zur Basis   sind starke Pseudoprimzahlen zur Basis   und können Teiler einer solchen sein. Mit der Basis 2 sind das die Wieferich-Primzahlen 1093 und 3511 (weitere sind bisher nicht bekannt).

Starke Pseudoprimzahlen lassen sich häufig als Produkte der Form

  mit
 ,
 und
 

ausdrücken. Umgekehrt ist der Anteil starker Pseudoprimzahlen bei solchen Produkten deutlich höher als bei ungeraden Zahlen allgemein.

Anzahl der Basen

Bearbeiten

Wenn die Primteiler einer zusammengesetzten Zahl   bekannt sind, kann die Anzahl der Basen, zu denen sie starke Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

   

ist die Anzahl der Basen   einschließlich 1 und n-1

 [8]  

Dabei ist

  •   der größte ungerade Teiler von   (wie oben)
  •   der größte ungerade Teiler von  ,
  •   der größte Exponent, mit dem  gilt, so dass  ist und
  •   das Minimum aller  .

Basen, zu denen eine zusammengesetze Zahl  keine Pseudoprimzahl ist, werden Zeugen für die Zusammengesetztheit der Zahl genannt; solche zu denen sie pseudoprim ist, werden „falsche Zeugen“ genannt. Maximal ein Viertel der teilerfremden Basen zwischen 0 und n sind falsche Zeugen.

Häufigkeit

Bearbeiten

Starke Pseudoprimzahlen zu einer festen Basis sind viel seltener als Primzahlen. Folgende Tabelle zeigt die Anzahl starker Pseudoprimzahlen zur Basis 2 im Vergleich zur Anzahl fermatscher Pseudoprimzahlen zur Basis 2 und der Primzahlen bis zur angegebenen Obergrenze.

Anzahl Starker Pseudoprimzahlen zur Basis 2 im Vergleich zu Primzahlen
Obergrenze Primzahlen[9] Fermatsche Pseudoprimzahlen Starke Pseudoprimzahlen[10]
  50.847.534 5.597 1.282
  37.607.912.018 101.629 22.407
  29.844.570.422.669 1.801.533 419.489
  24.739.954.287.740.860 33.763.684 8.646.507

Restklassen

Bearbeiten

Starke Pseudoprimzahlen liegen wesentlich häufiger in der Restklasse 1 modulo kleiner Zahlen   als in anderen Restklassen. Folgende Tabelle zeigt die Verteilung der starken Pseudoprimzahlen zur Basis 2 bis 1015 auf Restklassen modulo m an ein paar Beispielen.

Anzahl starker Pseudoprimzahlen zur Basis 2 in Restklasse
m 0 1 2 3 4 5 6 7
3 26 327193 92270
5 1373 199879 84716 74590 58931
7 370 142844 49224 62834 47482 57853 58882
8 0 207103 0 44885 0 122473 0 45028

Beispiele

Bearbeiten

Um zu zeigen, wie unterschiedlich starke Pseudoprimzahlen ausfallen können, werden als Beispiele die drei Zahlen 781, 1541 und 25 gezeigt. An der Zahl 781 wird erstmal die Zerlegung gezeigt:

Zerlegung

Gesucht wird das   zu einer Zahl   so dass   mit ungeradem   gilt. Die Formel können wir umstellen:

  •  
  •  
  •  

Am Beispiel der Zahl 781 sieht das so aus: Die Primfaktorzerlegung von  . Wenn man die 2er-Potenzen entfernt, bleibt für   das   übrig.

781 zur Basis 5

 

  also ist 781 eine starke Pseudoprimzahl zur Basis 5.

1541 zur Basis 5

 

  also ist 1541 eine starke Pseudoprimzahl zur Basis 5.

25 zur Basis 7

 

 

  also ist 25 eine starke Pseudoprimzahl zur Basis 7.

305 zur Basis 11

Dies ist ein Gegenbeispiel.

 

 

 

 

Somit ist 305 keine starke Pseudoprimzahl zur Basis 11.

  1.   Miller-Rabin-Test
  2.   Pseudoprimes and Fermat numbers
  3. Prime Numbers - A Computational Perspective, Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7 http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf
  4. The pseudoprimes to 25 * 10^9
  5. Glossar
  6.   Multiplicative order
  7. New Implementations for Tabulating Pseudoprimes and Liars.pdf
  8. On the number of false witnesses for a composite number, S. 270 (5.4)
  9.   Primzahlsatz
  10. Pseudoprime Statistics, Tables