Beweis des Lucas-Lehmer-Tests

10.02.2020, 21:51	MaPalui	Auf diesen Beitrag antworten »
Beweis des Lucas-Lehmer-Tests Hallo zusammen ich schaue mir gerade diesen Beweis zum LL-Test an. Dabei habe ich eine Frage zum Punkt (A10). Dort steht ja im Grunde $\begin{eqnarray} 2+\sqrt{3}\equiv \left(\frac{1+\sqrt{3}}{2} \right)^2 \pmod {M_n} \end{eqnarray}$ . Allerdings wurde in (A5) bereits festgestellt, dass 3 quadratischer Nichtrest modulo $\begin{eqnarray} M_n \end{eqnarray}$ ist. Darf ich dann einen Ausdruck der Form $\begin{eqnarray} 2+\sqrt{3}\pmod{M_n} \end{eqnarray}$ überhaupt betrachten? Freue mich auf eure Antworten LG Eure Maren
11.02.2020, 18:21	Elvis	Auf diesen Beitrag antworten »
$\begin{eqnarray} R((\frac{1+\sqrt 3}x)^2,m)=R(\frac {4+2\sqrt 3}2,m)=R(2+\sqrt 3 ,m) \end{eqnarray}$ Wegen $\begin{eqnarray} a=2<m,b=1<m \end{eqnarray}$ ist $\begin{eqnarray} m>2 \end{eqnarray}$ , also $\begin{eqnarray} 2+\sqrt 3 \mod m \end{eqnarray}$ nicht reduzierbar. Also ist $\begin{eqnarray} R(2+\sqrt 3 ,m)=2+\sqrt 3 \end{eqnarray}$ .
15.02.2020, 14:43	MaPalui	Auf diesen Beitrag antworten »
Hallo Elvis bitte entschuldige die späte Antwort. Dein Beitrag hat mir sehr geholfen und ich habe damit den Beweis auch insgesamt verstanden. Toll, ich danke dir vielmals LG Maren
15.02.2020, 15:31	Elvis	Auf diesen Beitrag antworten »
Den Lucas-Lehmer-Test habe ich am besten auf "mersenne.org, More Information, The Math" verstanden. Insgesamt eine sehr gute Website.
15.02.2020, 15:43	MaPalui	Auf diesen Beitrag antworten »
Da habe ich mich auch anfangs eingelesen und mir auch mal GIMPS zugelegt Aber wo wir gerade dabei sind, was macht GIMPS genau auf meinem PC? Also es gibt mir ja einen Exponenten, sagen wir $\begin{eqnarray} p \end{eqnarray}$ . Berechnet nun mein PC das Folgenglied $\begin{eqnarray} s_{p-1} \end{eqnarray}$ und prüft hinterher die Teilbarkeit durch $\begin{eqnarray} 2^p-1 \end{eqnarray}$ ? In dem Falle würde es mich nämlich einmal sehr interessieren, was denn nun genau die durchschnittlichen 10 Tage Rechenzeit verbraucht. Die Berechnung des Folgenglieds sollte doch vielleicht weniger das Problem sein, oder? Da es ja explizit berechenbar ist nehme ich doch mal an, die Folgenglieder bis zu einem bereits von einem anderen Teilnehmer berechneten Exponenten $\begin{eqnarray} p' \end{eqnarray}$ liegen vor und brauchen nun nicht mehr alzu lange. Ist die Berechnung von $\begin{eqnarray} 2^p-1 \end{eqnarray}$ der größte Teil der Leistung?
15.02.2020, 17:55	Elvis	Auf diesen Beitrag antworten »
Dort steht "The Lucas-Lehmer primality test is remarkably simple. It states that for $\begin{eqnarray} P > 2, 2^P-1 \end{eqnarray}$ is prime if and only if $\begin{eqnarray} S_{p-2} \end{eqnarray}$ is zero in this sequence: $\begin{eqnarray} S_0 = 4, S_N = (S_{N-1}^2 - 2) \mod (2^P-1) \end{eqnarray}$ ." Wahnsinnig große Zahlen berechnen und deren Primfaktoren suchen ist unmöglich. Der Test arbeitet rekursiv und benutzt schnelle Algorithmen für die Quadrierung großer Zahlen und Kongruenzrechnung.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »