Zitat von
Flocke:
Zitat von
Dr.Hackstable:
a,b,x,y seien 512-bit Zahlen die keinen ggt haben
Zitat von
negaH:
Berechne die Primfaktorzerlegung von a^x und b^y. Dann kannst du beide Tabellen der Primzahlexponenten jeweils bei gleicher Basis die Exponenten subtrahieren. Das was übrig ist ist die Tabelle der Primzahlexponenten von a^x/b^y und wird einfach ausmultipliziert.
Welche gleiche Basis ?
Die Basen der Primfaktorzerlegungen. Im Grunde hat man zwei Tabellen wie "2^e1 * 3^e2 * 5^e3 ..." für jeweils a^x und b^-y. Nun geht man diese Tabelle durch und subtrahiert jeweils die Exponenten aller gleichen Basen. Also wenn für a^x -> 2^e1 * .... und für b^y = 2^d1 *... gilt dann wird einfach 2^(e1-d1).... berechnet. Dies ist das endgültige Ergebniss als Primzahlfaktorzerlegung und muß dann nur noch ausmultipliziert werden.
Dies ist mit kleinen Zahlen noch machbar, aber nicht wenn alle 4 Parameter um die 512 Bit haben sollen, besonders nicht wenn die Exponenten so gigantisch sind.
Gruß Hagen