Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

a = x^y mod z <- hilfe

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Universitäts-Niveau » Zahlentheorie » a = x^y mod z <- hilfe « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Sebastian (sebbi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Neues Mitglied
Benutzername: sebbi

Nummer des Beitrags: 1
Registriert: 07-2002
Veröffentlicht am Mittwoch, den 10. Juli, 2002 - 13:00:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: zaph

Nummer des Beitrags: 1216
Registriert: 07-2000
Veröffentlicht am Mittwoch, den 10. Juli, 2002 - 23:50:   Beitrag drucken

Ist wohl nicht das, was du suchst?

for(x=0; x<z; x++) if(pow(x,y)%z == a) printf("x = %d",x);

Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Sebastian (sebbi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Neues Mitglied
Benutzername: sebbi

Nummer des Beitrags: 2
Registriert: 07-2002
Veröffentlicht am Freitag, den 12. Juli, 2002 - 01:26:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 527
Registriert: 05-2000
Veröffentlicht am Freitag, den 12. Juli, 2002 - 12:22:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: zaph

Nummer des Beitrags: 1220
Registriert: 07-2000
Veröffentlicht am Freitag, den 12. Juli, 2002 - 19:44:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 528
Registriert: 05-2000
Veröffentlicht am Samstag, den 13. Juli, 2002 - 01:00:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: zaph

Nummer des Beitrags: 1223
Registriert: 07-2000
Veröffentlicht am Samstag, den 13. Juli, 2002 - 15:47:   Beitrag drucken

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.

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page