Problem bei Lucas-Lehmer-Test |
| 23.06.2011, 21:24 | Luciee131 | Auf diesen Beitrag antworten » |
| Problem bei Lucas-Lehmer-Test Hallo alle zusammen! Ich habe einen kleinen gedanklichen Hänger bei der Herleitung des Lucas-Lehmer-Tests aus den Lucas-Folgen. Es N = M_n = 2^n - 1 eine Mersenne-Zahl und U_n und V_n die Lucas-Folgen. Damit nun m_n eine Primzahl ist muss gelten U_(N+1) kongruent 0 (mod N) und U_((n+1)/2) inkongruent 0 (mod N). Das ist auch kein Problem, da ich mich vorher eingehend mit Lucas-Folgen und den darauf beruhenden Primzahltests beschäftigt habe. Es gilt nun U_(N+1) = U_((n+1)/2)* V_((n+1)/2. auch verstanden, kann man mit Eigenschaften über Lucas-Folgen gut erkennen. Damit nun die obige Bedingung erfüllt ist, muss man zeigen, dass V_((n+1)/2) = V_(2^(n-1)) kongruent 0 (mod n) ist. bis dahin auch kein Problem. Man substitutiert nun indem man setzt V_(2^s) = v_s und erhält mit Hilfe der Eigenschaften über Lucas-Folgen dass gilt V_(2^s) = v_s = (v_(s-1))^2 - 2Q^(2^(s-1)). Man setzt nun als v_0 = P. Bis dahin alles verstanden. Nun steht hier: Sei v_s kongruent (v_(s-1))^2 - 2Q^(2^(s-1)) (mod N) dann ist die Bedingung V_((n+1)/2) = V_(2^(n-1)) kongruent 0 (mod N) gleichzusetzen mit v_(n-1) kongruent 0 (mod M_n) Meine Frage ist nun, warum muss gelten V_((n+1)/2) = V_(2^(n-1)) kongruent 0 (mod N). Meine Ideen: Ich sehe auch schon ohne diese Kongruenz dass man überprüfen muss, dass v_(n-1) kongruent 0 (mod M_n) ist, da man ja substitutiert hat und ich berechne somit weil V_(2^s) = v_s gilt auch V_(2^(n-1))= V_((n+1)/2) = v_(n-1). Wie ihr seht hakt es nur an einer Stelle. Und noch eine ganz Kleinigkeit, man rechnet dann mit P = 2 und Q = 2 und in diesem Buch steht dann v_s = (v_(s-1))^2 - 2Q^(2^(s-1)) = (v_(s-1))^2 - 2 * 2(2^(s-1)). Warum steht da kein + denn minus mal minus gibt doch +??? Vielen Dank für eure Antworten! |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
Wichtig: