Lucas-Lehmer-Primzahltest -

Lucas–Lehmer primality test

${\displaystyle 2^{\frac {M_{p}-1}{2}}\äquiv 1{\pmod {M_{p}}}.}$

Die Kombination dieser beiden Äquivalenzrelationen ergibt

${\displaystyle 24^{\frac {M_{p}-1}{2}}\equiv \left(2^{\frac {M_{p}-1}{2}}\right)^{3}\ left(3^{\frac{M_{p}-1}{2}}\right)\equiv (1)^{3}(-1)\equiv -1{\pmod {M_{p}}}. }$

${\displaystyle {\begin{ausgerichtet}(6+\sigma)^{M_{p}}&=6^{M_{p}}+\left(2^{M_{p}}\right)\left( {\sqrt {3}}^{M_{p}}\right)\\&=6+2\left(3^{\frac {M_{p}-1}{2}}\right){\sqrt {3}}\\&=6+2(-1){\sqrt {3}}\\&=6-\sigma ,\end{ausgerichtet}}}$

wobei die erste Gleichheit den Binomialsatz in einem endlichen Körper verwendet , der

${\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}$

,

und die zweite Gleichheit verwendet den kleinen Satz von Fermat , der

${\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}$

${\displaystyle \sigma}$

${\displaystyle {\begin{ausgerichtet}\omega ^{\frac {M_{p}+1}{2}}&={\frac {(6+\sigma)^{M_{p}+1}}{ 24^{\frac{M_{p}+1}{2}}}}\\&={\frac {(6+\sigma)(6+\sigma)^{M_{p}}}{24\ cdot 24^{\frac {M_{p}-1}{2}}}}\\&={\frac {(6+\sigma)(6-\sigma)}{-24}}\\&= -1.\end{ausgerichtet}}}$

Es bleibt nur noch, beide Seiten dieser Gleichung mit zu multiplizieren und zu verwenden , was ergibt

${\displaystyle {\bar {\omega}}^{\frac {M_{p}+1}{4}}}$

${\displaystyle {\begin{ausgerichtet}\omega ^{\frac {M_{p}+1}{2}}{\bar {\omega}}^{\frac {M_{p}+1}{4} }&=-{\bar {\omega}}^{\frac {M_{p}+1}{4}}\\\omega ^{\frac {M_{p}+1}{4}}+{ \bar {\omega}}^{\frac {M_{p}+1}{4}}&=0\\\omega ^{\frac {2^{p}-1+1}{4}}+ {\bar {\omega}}^{\frac {2^{p}-1+1}{4}}&=0\\\omega ^{2^{p-2}}+{\bar {\ Omega }}^{2^{p-2}}&=0\\s_{p-2}&=0.\end{ausgerichtet}}}$

S P − 2 {\displaystyle s_{p-2}} m P . {\displaystyle M_{p}.}

Anwendungen

Der Lucas-Lehmer-Test ist der Primalitätstest, der von der Great Internet Mersenne Prime Search (GIMPS) verwendet wird, um große Primzahlen zu lokalisieren. Diese Suche war erfolgreich beim Auffinden vieler der größten bisher bekannten Primzahlen. Der Test wird als wertvoll erachtet, da er wahrscheinlich innerhalb eines erschwinglichen Zeitraums eine große Menge sehr großer Zahlen auf Primalität testen kann. Im Gegensatz dazu kann der äquivalent schnelle Pépin-Test für jede Fermat-Zahl nur auf eine viel kleinere Menge sehr großer Zahlen angewendet werden, bevor die Rechengrenzen erreicht werden.

Siehe auch

• Mersennes Vermutung
• Lucas-Lehmer-Riesel-Test

Anmerkungen

1. ^
   Formal lassen Sieund.

   ${\displaystyle \mathbb{Z}_{q}=\mathbb{Z} /q\mathbb{Z}}$
2. ω + Ich T 2 − 3 Ich {\displaystyle \omega +\langle T^{2}-3\rangle} ω ¯ + Ich T 2 − 3 Ich {\displaystyle {\bar{\omega}}+\langle T^{2}-3\rangle} ω {\displaystyle\omega} ω ¯ {\displaystyle {\bar {\omega}}} Z [ 3 ] {\displaystyle \mathbb {Z} [{\sqrt {3}}]} 3 {\displaystyle {\sqrt {3}}}

Verweise

• Crandall, Richard ; Pomerance, Carl (2001), "Section 4.2.1: The Lucas-Lehmer test", Primzahlen: A Computational Perspective (1. Aufl.), Berlin: Springer, p. 167–170, ISBN 0-387-94777-9

Externe Links

• Weisstein, Eric W. "Lucas-Lehmer-Test" . MathWorld .
• GIMPS (Die große Internet-Mersenne-Prime-Suche)
• Ein Beweis des Lucas-Lehmer-Reix-Tests (für Fermat-Zahlen)
• Lucas-Lehmer-Test im MersenneWiki