PW finden mit Jacobi

Neue Frage »

Joe33 Auf diesen Beitrag antworten »
PW finden mit Jacobi
Meine Frage:
Für modulo m mit m=5^10 ist eine Primitivwurzel zu finden.

Meine Ideen:
Da 5 eine Primzahl ist, reicht es eine PW in 5^2 zu finden. Bestimme zunächst phi(25)=20 also ord(a)=20 mod 25.

Aber wie finde ich jetzt eine Zahl a, bei der der Exponent 20 der kleinste ist, so dass a^20 = 1 mod 25??
tatmas Auf diesen Beitrag antworten »

Wenn dir gar nichts anderes einfällt:
Ausprobieren. D.h. immerhin eine 40% Trefferwahrscheinlichleit.
joe331 Auf diesen Beitrag antworten »

Also soll ich jetzt alle Zahlen von 2-24 ausprobieren und schauen wann 20 dafür der kleinste (!!) Exponent ist damit 1 rauskommt?


EDIT(Helferlein): Neuen Threat mit derselben Fragestellung hier angefügt und alles gelöscht, was nicht mit der Beantwortung der Frage zu tun hat.
tatmas Auf diesen Beitrag antworten »

Du wirst nicht so viele ausprobieren müssen. Wie gesagt 40% sind hier Primitvwurzeln.
Und ja du musst schauen ob die Ordnung 20 ist.
Ich gehe davon aus, du weißt wie man das effizient macht.

Übrigens ist hier 24=-1 hat also Ordnung 2 kann man sich gleich schenken.
joe331 Auf diesen Beitrag antworten »

Ich weiss nicht wirklich wie man das effizient macht.. vielleicht kannst du mir das erläutern.
HAL 9000 Auf diesen Beitrag antworten »

Für ungerade Primzahlen gilt: Damit Primitivwurzel modulo ist, muss es notwendig Primitivwurzel modulo sein.

Es lohnt sich daher, zumindest eine Primitivwurzel modulo zu bestimmen, nennen wir sie . Primitivwurzel(n) sucht man dann in der schon deutlich kleineren Kandidatenmenge .
 
 
joe331 Auf diesen Beitrag antworten »

Also eine PW modulo 5 wäre ja 2 da ord (2)=4=phi(5) also wäre die Menge dann {2,7,12,17,24} in der ich weiter suchen würde.

Aber wie überprüfe ich jetzt ob z.b ord (7)=20 ?
HAL 9000 Auf diesen Beitrag antworten »

Betrachten wir für eine Primitivwurzel deren Ordnung bzgl. : Dann ist , also klar. Andererseits gilt wegen der Primitivwurzeleigenschaft auch , es bleiben also nur die Möglichkeiten oder . Man muss also nur ersteres ausschließen, damit auch Primitivwurzel ist, dafür ist also lediglich zu prüfen.
Neue Frage »
Antworten »



Verwandte Themen

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