Zum Inhalt springen

Lucas-Test (Mathematik)

aus Wikipedia, der freien Enzyklopädie

{{#if: erläutert den Primzahltest für natürliche Zahlen n, für die die Faktorisierung von n−1 bekannt ist. Zum Primzahltest für Mersenne-Zahlen siehe Lucas-Lehmer-Test. 

 | Vorlage:Hinweisbaustein 
 | {{#ifeq: 0 | 0 |}}

}} Der Lucas-Test ist eine Weiterentwicklung des Fermatschen Primzahltests durch den Mathematiker Édouard Lucas. Der Test wurde in den 1950er Jahren von Derrick Henry Lehmer und später nochmals von John Brillhart und John L. Selfridge verbessert. Er sollte nicht mit dem Lucas-Lehmer-Test für Mersenne-Zahlen verwechselt werden.

Fermatscher Primzahltest

Gegeben sei eine natürliche Zahl <math>n > 1</math>, für die man prüfen möchte, ob sie prim ist. Nach dem fermatschen Primzahltest ist <math>n</math> keine Primzahl, wenn folgende Bedingung für eine zu <math>n</math> teilerfremde Zahl <math>a</math> mit <math>1<a<n</math> zutrifft:

<math>a^{n-1} \not\equiv 1 \pmod n</math>

Der Fermat-Test liefert also niemals die Aussage, dass eine Zahl prim ist, sondern kann nur das Prim-Sein ausschließen. Für die Carmichael-Zahlen liefert der Fermat-Test keine Aussage.

Lucas-Test

Im Jahr 1876 gelang Édouard Lucas folgende Umkehrung des kleinen fermatschen Satzes:

(Vorläufer des Lucas-Tests) Eine natürliche Zahl <math>n</math> ist genau dann eine Primzahl, wenn es ein <math>a</math> mit <math>1<a<n</math> gibt, für das

<math>a^{n-1} \equiv 1 \pmod n</math>

sowie

<math>a^m \not\equiv 1 \pmod n</math>

für alle natürlichen Zahlen <math>m<n-1</math> gilt.

Dieses Ergebnis lässt sich nur schwer anwenden, da so viele <math>m</math> geprüft werden müssen. Im Jahr 1891 verbesserte Lucas den Satz und erhielt den nach ihm benannten Primzahltest:

(Lucas-Test) Eine natürliche Zahl <math>n</math> ist genau dann eine Primzahl, wenn es ein <math>a</math> mit <math>1<a<n</math> gibt, für das

<math>a^{n-1} \equiv 1 \pmod n</math>

sowie

<math>a^m \not\equiv 1 \pmod n</math>

für alle echten Teiler <math>m<n-1</math> von <math>n-1</math> gilt.<ref>Beweise hierzu: siehe Ribenboim, Die Welt der Primzahlen, Seite 40.</ref>

Da hier nur noch die Teiler von <math>n-1</math> getestet werden müssen, sind erheblich weniger Rechenschritte nötig. Ein Nachteil ist jedoch, dass man die Primfaktorzerlegung von <math>n-1</math> kennen muss. <math>n-1</math> muss also faktorisiert werden. Für Zahlen mit einem besonderen Aufbau ist diese Methode aber sehr effizient, so zum Beispiel bei Zahlen der Form <math>2^k+1</math>.

Ist die Bedingung des Lucas-Tests für eine Basis <math>a</math> nicht erfüllt, so folgt nicht, dass die Zahl <math>n</math> zusammengesetzt ist. Dafür müsste man nämlich alle Basen <math>1<a<n</math> prüfen.

Beispiel:

Für die Zahl <math>n=59</math> gilt <math>2^{58}\equiv 1 \bmod 59</math>. Die echten Teiler von <math>n - 1 = 58</math> sind <math>1, 2</math> und <math>29</math>. Weiter gilt <math>2^1 \equiv 2 \bmod 59, 2^2\equiv 4 \bmod 59</math> und <math>2^{29}\equiv -1 \bmod 59</math>. Es folgt, dass <math>59</math> eine Primzahl ist.

Erweiterungen von Lehmer, Brillhart und Selfridge

Derrick Henry Lehmer fand 1953 den verbesserten Lucas-Test. Im Jahr 1967 wurde eine weitere Version (flexibler Lucas-Test) von John Brillhart und John L. Selfridge entdeckt.

Verbesserter Lucas-Test

Der verbesserte Lucas-Test beruht auf folgender Eigenschaft:
<math>n</math> ist genau dann eine Primzahl, wenn es eine natürliche Zahl <math>a</math> mit <math>1<a<n</math> gibt, für die

<math>a^{n-1}\equiv 1 \pmod n</math>

sowie

<math>a^{\frac{n-1}{q_i}} \not\equiv 1 \pmod n</math>

für alle Primfaktoren <math>q_i</math> von <math>n-1</math> gilt.

Die Anwendung dieses Tests auf Fermat-Zahlen wird mit Pépin-Test bezeichnet.

Flexibler Lucas-Test

Der flexible Lucas-Test beruht auf folgender Eigenschaft:
Für die natürliche Zahl <math>n</math> sei die Primfaktorzerlegung von <math>n-1</math> gegeben durch

<math>n-1=q_1^{e_1} \cdot \ldots \cdot q_r^{e_r}</math>.

Dann gilt: <math>n</math> ist genau dann eine Primzahl, wenn es zu jedem Primfaktor <math>q_i</math> eine natürliche Zahl <math>a_i</math> mit <math>1<a_i<n</math> gibt, für die

<math>a_i^{n-1} \equiv 1 \pmod n</math>

sowie

<math>a_i^{\frac{n-1}{q_i}} \not\equiv 1 \pmod n</math>

gilt.<ref>Zum Beweis dieses und des vorigen Satzes siehe Ribenboim, Die Welt der Primzahlen, Seite 42.</ref>

Beispiel

Wir betrachten die Primzahl <math>n=911</math>. Die Vorgängerzahl <math>n-1=910</math> hat die Primteiler <math>q = 2, 5, 7</math> und <math>13</math>. Die folgende Tabelle zeigt dazu passende <math>a</math> und wie die Bedingungen erfüllt werden:

q a an-1 ≡ 1 (mod n) a(n-1)/q ≢ 1 (mod n)
2 7 7910 ≡ 1 (mod 911) 7910/2 ≡ -1 (mod 911)
5 3 3910 ≡ 1 (mod 911) 3910/5 ≡ 482 (mod 911)
7 2 2910 ≡ 1 (mod 911) 2910/7 ≡ 568 (mod 911)
13 2 2910 ≡ 1 (mod 911) 2910/13 ≡ 577 (mod 911)

Pratt Primzahltest

Der Pratt-Test ist ein iterierter Lucas-Test.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Daniela Steidl|Daniela Steidl: }}{{#if:|{{#if:Primzahlzertifikat von Pratt|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Primzahlzertifikat von Pratt}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Primzahlzertifikat von Pratt}}}}|[{{#invoke:URLutil|getNormalized|1=https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Primzahlzertifikat von Pratt}}}}]}}{{#if:| ({{{format}}}{{#if:2008-04-17{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:de|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf}}%7C%7C}}}}{{#if:Primzahlzertifikat von Pratt|{{#if:{{#invoke:WLink|isValidLinktext|1=Primzahlzertifikat von Pratt|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=}}}}{{#if: | {{#if: 2008-04-17|,|{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2008-04-17| {{#if:{{#invoke:DateTime|format|2008-04-17|noerror=1}}
            |{{#invoke:DateTime|format|2008-04-17|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2008-04-17|class=Zitationswartung}} }}{{#if: |,|{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2008-04-17|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:205895||(?)}}}}}}{{#if: 2020-05-07|;}}}}{{#if: 2020-05-07| {{#if:2008-04-17{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2020-05-07 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2020-05-07|class=Zitationswartung}} }} {{#invoke:DateTime|format|2020-05-07|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:de|1}}}}|{{#if:2008-04-17{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|de|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2008-04-17{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}de|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref><ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:apl. Prof. Dr. Klaus Reinhardt|apl. Prof. Dr. Klaus Reinhardt: }}{{#if:|{{#if:Pratt Primzahlentest|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Pratt Primzahlentest}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Pratt Primzahlentest}}}}|[{{#invoke:URLutil|getNormalized|1=https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Pratt Primzahlentest}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de,en|de||{{#if:de,en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html}}%7C%7C}}}}{{#if:Pratt Primzahlentest|{{#if:{{#invoke:WLink|isValidLinktext|1=Pratt Primzahlentest|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=}}}}{{#if: | {{#if: |,|{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format||noerror=1}}
            |{{#invoke:DateTime|format||T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=|class=Zitationswartung}} }}{{#if: |,|{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:205895||(?)}}}}}}{{#if: 2020-05-07|;}}}}{{#if: 2020-05-07| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2020-05-07 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2020-05-07|class=Zitationswartung}} }} {{#invoke:DateTime|format|2020-05-07|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de,en|de||{{#if:de,en|1}}}}|{{#if:{{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de,en|de,en|de}}|de||
          {{#invoke:Multilingual|format|de,en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de,en|de,en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2020-05-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}de,en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html
       | {{#if:  | [3] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html
       | {{#if:  | [4] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> Für alle Primfaktoren von <math>n-1</math> wird wiederum geprüft, ob diese Primzahlen sind.

Fermat-Paar

<math>(a,b)</math> ist ein Fermat-Paar, falls <math>(a,b)=(1,2) \lor (a\geq 2 \land a^{n-1} \not\equiv 1 \mod n)</math>

Pratt-Sequenz

<math>(a_1,b_1) \dots (a_k,b_k)</math> ist eine Pratt-Sequenz, wenn für jedes Fermat-Paar <math>(a,b)</math> aus der Sequenz gilt, dass für jeden Primfaktor <math>p</math> von <math>b</math> ein Fermat-Paar <math>(a', p)</math> in der Prattsequenz enthalten ist und es gilt: <math>a^{\frac{n-1}{p}} \not\equiv 1</math>


Für jede Primzahl gibt es eine Pratt-Sequenz in der Länge der Darstellung der Primzahl, weshalb <math> Prime \in NP </math>.

Beispiel

Für <math>797</math> ist folgendes eine Mögliche Pratt-Sequenz

<math>(5,797),(1,2),(6,199),(5,3),(3,11)</math>

zu überprüfen ist nun noch, ob <math>a^{b-1}\equiv 1</math> und danach, ob für die Primteiler <math>p</math> von <math> b-1 </math> gilt, <math> a^{\frac{b-1}{2}} \not\equiv </math>


<math>(5,797)</math>

<math>5^{797-1} \mod 797 \equiv 5^{796} \mod 797 \equiv 1</math>

<math>5^{\frac{796}{2}} \mod 797 \equiv 5^{398} \mod 797 \equiv 796 \not\equiv 1</math>

<math>5^{\frac{796}{199}} \mod 797 \equiv 5^{4} \mod 797 \equiv 625 \not\equiv 1</math>


<math>(6,199)</math>

<math>6^{199-1} \mod 199 \equiv 6^{198} \mod 199 \equiv 1</math>

<math>6^{\frac{198}{2}} \mod 199 \equiv 6^{99} \mod 199 \equiv 198 \not\equiv 1</math>

<math>6^{\frac{198}{3}} \mod 199 \equiv 6^{66} \mod 199 \equiv 192 \not\equiv 1</math>

<math>6^{\frac{198}{11}} \mod 199 \equiv 6^{18} \mod 199 \equiv 63 \not\equiv 1</math>


<math>(5,3)</math>

<math>5^{3-1} \mod 3 \equiv 5^{2} \mod 3 \equiv 1</math>

<math>5^{\frac{2}{2}} \mod 3 \equiv 5^{1} \mod 3 \equiv 2 \not\equiv 1</math>


<math>(2,5)</math>

<math>2^{5-1} \mod 5 \equiv 2^{4} \mod 5 \equiv 1</math>

<math>2^{\frac{2}{2}} \mod 5 \equiv 2^{1} \mod 5 \equiv 2 \not\equiv 1</math>

Literatur

  • Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin u. a. 2006, ISBN 3-540-34283-4 (Springer-Lehrbuch).
  • John Brillhart, D. H. Lehmer, J. L. Selfridge: New Primality Criteria and factorizations of <math>2^n \pm 1</math>. In: Mathematics of Computation. 29, 1975, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0025-5718|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1 

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0 

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0025-5718}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, S. 620–647, online (PDF; 2,14 MB).

Einzelnachweise

<references/>

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Lucas-Test_(Mathematik)&oldid=205895“