PW finden mit Jacobi |
09.06.2018, 22:19 | Joe33 | Auf diesen Beitrag antworten » |
PW finden mit Jacobi 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?? |
||
09.06.2018, 22:31 | tatmas | Auf diesen Beitrag antworten » |
Wenn dir gar nichts anderes einfällt: Ausprobieren. D.h. immerhin eine 40% Trefferwahrscheinlichleit. |
||
10.06.2018, 12:05 | 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. |
||
10.06.2018, 12:35 | 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. |
||
10.06.2018, 12:56 | joe331 | Auf diesen Beitrag antworten » |
Ich weiss nicht wirklich wie man das effizient macht.. vielleicht kannst du mir das erläutern. |
||
10.06.2018, 13:51 | 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 . |
||
Anzeige | ||
|
||
10.06.2018, 21:10 | 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 ? |
||
10.06.2018, 21:40 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|