Suche der ersten Primitivwurzel - gibt es geschickteres Vorgehen als alle Zahlen 2,3,4,.. zu testen? |
12.01.2013, 16:37 | Very | Auf diesen Beitrag antworten » | ||
Suche der ersten Primitivwurzel - gibt es geschickteres Vorgehen als alle Zahlen 2,3,4,.. zu testen? im Rahmen eines anderen Threads (Zahlentheorie Berechne Primitivwurzeln von 17, nicht erwartete Anzahl von Primitivwurzeln erhalten), hats ich bei mir noch eine weitere Frage bei der Suche nach Primitivwurzeln ergeben, die dort nicht beantwortet werden konnte. Da diese mittlerweile vom anderen Thema abweicht, eröffne ich jetzt einen neuen Thread. Wie gesagt geht es um die Suche von Primitivwurzeln zu einer ungeraden Primzahl (für p=2 gibt es meines Wissens nach ja keine Primitivwurzeln). Sobald ich eine Primitivwurzel gefunden habe, kann ich die andern leicht über ein Standardverfahren finden. Doch: wie finde ich die erste Primitivwurzel? Gibt es da ein bestimmtes Vorgehen? ich würde einfach bei 2 angefangen, hätte dann bei 3,4,5,6,7,... weitergemacht. Ist das richtig so? Oder gibt es ein geschickteres Vorgehen? Würde mich über Hilfe sehr freuen. lg Very |
||||
12.01.2013, 16:44 | Mystic | Auf diesen Beitrag antworten » | ||
RE: Suche der ersten Primitivwurzel - gibt es geschickteres Vorgehen als alle Zahlen 2,3,4,.. zu tes
Im Prinzip nein, außer dass du gewisse Zahlen in deiner Folge weglassen kannst... Ist nämlich z.B. 2 keine Primitivwurzel, dann sind die Potenzen mit k>1 erst recht keine... |
||||
12.01.2013, 16:52 | Very | Auf diesen Beitrag antworten » | ||
Wenn ich das richtig verstanden habe, heißt das: 1. Teste 2 --> 2 ist PW fertig oder 2 ist keine PW --> schließe , ,... aus (natürlich immer modulo p) 2. Teste 3 --> 3 ist PW fertig oder 3 ist keine PW --> schließe ,... aus (natürlich immer modulo p) 3. Teste 4 (nicht nötig, da nach 1. ausgeschlossen) 4. Teste 5 ... und damit spare ich mir in dem Fall z.B. die Überprüfung von 4. Welche Fälle ich mir genau spare, hängt natürlich immer von dem gegegenen p ab. Passt das so? |
||||
12.01.2013, 17:20 | Mystic | Auf diesen Beitrag antworten » | ||
Ja, so kann man das auf jeden Fall machen... |
||||
12.01.2013, 17:34 | Very | Auf diesen Beitrag antworten » | ||
ok, vielen Dank für die Hilfe |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|