Beweis des Lucas-Lehmer-Tests

Neue Frage »

MaPalui Auf diesen Beitrag antworten »
Beweis des Lucas-Lehmer-Tests
Hallo zusammen smile

ich schaue mir gerade diesen Beweis zum LL-Test an.
Dabei habe ich eine Frage zum Punkt (A10). Dort steht ja im Grunde .
Allerdings wurde in (A5) bereits festgestellt, dass 3 quadratischer Nichtrest modulo ist.
Darf ich dann einen Ausdruck der Form überhaupt betrachten?

Freue mich auf eure Antworten smile

LG
Eure Maren
Elvis Auf diesen Beitrag antworten »


Wegen ist , also nicht reduzierbar.
Also ist .
 
 
MaPalui Auf diesen Beitrag antworten »

Hallo Elvis smile

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 smile

LG
Maren
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.
MaPalui Auf diesen Beitrag antworten »

Da habe ich mich auch anfangs eingelesen und mir auch mal GIMPS zugelegt Augenzwinkern

Aber wo wir gerade dabei sind, was macht GIMPS genau auf meinem PC?
Also es gibt mir ja einen Exponenten, sagen wir . Berechnet nun mein PC das Folgenglied und prüft hinterher die Teilbarkeit durch ?
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 liegen vor und brauchen nun nicht mehr alzu lange.
Ist die Berechnung von der größte Teil der Leistung?
Elvis Auf diesen Beitrag antworten »

Dort steht "The Lucas-Lehmer primality test is remarkably simple. It states that for is prime if and only if is zero in this sequence: ."
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »