Autor |
Beitrag |
Sebastian (sebbi)
Neues Mitglied Benutzername: sebbi
Nummer des Beitrags: 1 Registriert: 07-2002
| Veröffentlicht am Mittwoch, den 10. Juli, 2002 - 13:00: |
|
Hallo Leute ich brauch dringend hilfe bei dem oben genannte Problem. Ich soll ein Programm schreiben, was x bei gegebenen a, y und z berechnet. Leider fehlt mir jede Idee. Das Problem ist also x zu ermitteln, wenn a, y und z variieren. a = x^y mod z Danke |
Zaph (zaph)
Senior Mitglied Benutzername: zaph
Nummer des Beitrags: 1216 Registriert: 07-2000
| Veröffentlicht am Mittwoch, den 10. Juli, 2002 - 23:50: |
|
Ist wohl nicht das, was du suchst? for(x=0; x<z; x++) if(pow(x,y)%z == a) printf("x = %d",x);
|
Sebastian (sebbi)
Neues Mitglied Benutzername: sebbi
Nummer des Beitrags: 2 Registriert: 07-2002
| Veröffentlicht am Freitag, den 12. Juli, 2002 - 01:26: |
|
Nein, leider nicht. Ein Bruteforce dauert zu lange. Vor allem, wenn es sich um größere Zahlen, wie 160 bit oder mehr handelt. Vielleicht kann mir auch jemand helfen, wie man diese Gleichung nach x umstellen kann. Ich möchte mich nicht mit dem Gedanken zu Frieden stellen, das Bruteforce der einzigste Weg ist. |
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 527 Registriert: 05-2000
| Veröffentlicht am Freitag, den 12. Juli, 2002 - 12:22: |
|
Hi sebbi Meines Wissens nach ist sogar die Entscheidung, ob eine Zahl ein Quadrat modulo z ist, NP-vollständig, oder zumindest wird angenommen, dass sie nicht in Polynomialzeit lösbar ist. Deine Aufgabe ist offensichtlich mindestens genauso schwierig, daher gibt es wahrscheinlich keine essentiell bessere Lösung, als irgendwas Exponentielles. viele Grüße SpockGeiger |
Zaph (zaph)
Senior Mitglied Benutzername: zaph
Nummer des Beitrags: 1220 Registriert: 07-2000
| Veröffentlicht am Freitag, den 12. Juli, 2002 - 19:44: |
|
Ganz so schlimm, wie Spockgeiger es darstellt, ist es nicht. Die Frage, ob eine Zahl ein Quadrat ist, lässt sich sogar sehr elegant programmieren. (Stichwort: Reziprozitätsgesetz) Für die allgemeine y-te Wurzel ist allerdings kein Algorithmus bekannt. Ausnahme: z ist prim. |
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 528 Registriert: 05-2000
| Veröffentlicht am Samstag, den 13. Juli, 2002 - 01:00: |
|
Hi Zaph Beide Algorithmen würden mich sehr interessieren, könntest Du sie wohl hier reinschreiben, oder ne Quelle angeben, bitte= viele Grüße SpockGeiger |
Zaph (zaph)
Senior Mitglied Benutzername: zaph
Nummer des Beitrags: 1223 Registriert: 07-2000
| Veröffentlicht am Samstag, den 13. Juli, 2002 - 15:47: |
|
Das mit dem Reziprozitätsgesetz funktioniert wohl doch nur, wenn z prim. Allgemein gilt aber: Wenn y * d = 1 mod phi(z), dann ist a^d = x mod z. Hierbei ist phi die eulersche Phi-Funktion. Problem 1: Berechnung von phi(z), insbesondere, wenn z mehrere große Faktoren besitzt. Problem 2: Wenn ggt(y,phi(z)) > 1, dann gibt es solch ein d nicht. Spezialfall zu Problem 2: Gesucht ist x mit x² = a mod z und z prim. Wenn z = 3 mod 4, setze x = a^((p-1)/4) mod z oder x = -a^((p-1)/2) mod z. Probe machen!! Wenn z = 1 mod 4, gibt es ebenfalls einen Algorithmus, ist aber wesentlich komplizierter. Habe ich jetzt auch nicht parat. Wenn z. B. y = 6, dann erst die zweite und dann die dritte Wurzel ziehen. Auch hilfreich kann folgendes sein: Wenn z = z1 * ... * zn mit ggt(zi,zj) = 1 für i ungleich j, bestimme zunächst xi, sodass xi^y = a mod zi. Bestimme dann x mit x = xi mod zi für i = 1,...,n. |
|