Rechnen mit Modulo Potenzen?
Moinsen, ich beschäftige mich im Moment mit der Berechnung von Modulo Potenzen, z.B. aktuell ist es die 42^23 mod 3127.
Mein Problem liegt hierbei, dass ich Ewigkeiten brauche um das manuell auszurechnen. Das sind riesige Zahlen :-/ allein 42^2 mod 3127 = 1764 zeigt mir schon, dass die Zahlen echt groß sind und das lange dauert.
Habe mir einige Videos zu Restklassen angeschaut und weiß z.B. dass 7^98 mod 5 das gleiche ist wie 2^98 mod 5, das kann ich dann in (2^2)49 mod 5 ändern und 4^49 ist in der gleichen Restklasse wie (-1)^49, somit ist das ganze einfach.
Aber bei einer Zahl so groß wie mod 3127 hab ich keine Ahnung wie ich da vernünftig vorgehen kann ohne diese ganzen großen Zahlen jedes mal aufs neue schriftlich zu multiplizieren und dividieren, und das geht teilweise über Millionensummen hinaus
normalerweise würde ich gucken, dass ich die 16er, 4er und 3er Potenz mod n, also 42^16, 42^4 und 42^3 mod n berechne, diese dann multipliziere und mod n rechne. Aber um 42^16 zu bestimmen muss ich auch 42^4 und 42^8 bestimmen und diese Zahlen werden riesig sein und dann denke ich mir das ist doch nicht der Weg um sowas zu lösen :D
2 Antworten
3127 = 53 × 59
42^23 mod 53 = (-11)^23 mod 53 = - 11^23 mod 53
= - (((11^2)^2 * 11)^2 * 11)^2* 11 mod 53 = 44 mod 53 = -9 mod 53
42^23 mod 59 = - 17^23 mod 59
= - (((17^2)^2 * 17)^2 * 17)^2* 17 mod 59 = 56 mod 59 = -3 mod 59
Jetzt muss man noch der Chinesischen Restsatz anwenden, um die Lösung mod 3127 zu erhalten.
= - (((11^2)^2 * 11)^2 * 11)^2* 11 mod 53
Man kann nach jedem Schritt wieder mod 53 rechnen,
= - ((121^2 * 11)^2 * 11)^2* 11 mod 53
= - ((15^2 * 11)^2 * 11)^2 * 11 mod 53
= - ((225 * 11)^2 * 11)^2 * 11 mod 53
= - ((13 * 11)^2 * 11)^2 * 11 mod 53
= - (143^2 * 11)^2 * 11 mod 53
= - ((-16)^2 * 11)^2 * 11 mod 53
= - (256 * 11)^2 * 11 mod 53
= - (-7 * 11)^2 * 11 mod 53
= - 484^2 * 11 mod 53
= - (-7)^2 * 11 mod 53
= - 49 * 11 mod 53
= 4 * 11 mod 53
= 44 mod 53
Der erweiterte euklidische Algorithmus ist mit M= m1 * m2 = 3127 für m1 = 53, M1= 3127/53= 59 und m2 = 59, M2= 3127/59= 53 durchzuführen.
Primteiler des zu betrachtenden Modulus finden, dann bzgl. des jeweiligen Modulus reduzieren, schliesslich Chinesischen Restsatz anwenden - ich hätte es ausführlich vorgerechnet, muss jetzt aber schlafen gehen… :-)
Stimmt, 53 und 59 sind die beiden Primzahlen die ich verwendet habe um mein n = 3127 zu erhalten. Aber wie bist du darauf gekommen? :O
Dann nimmst du die gesuchte Zahl mod 53 - die -11 ist in der gleichen Restklasse und macht es etwas einfacher zu rechnen, also ist die gesuchte zahl -11^23 mod 53
die nächste Gleichung erschließt sich mir nicht ganz 11^2 -> 11^4 -> 11^5 -> (11^5)^2* 11 wieso ist das = 44 bzw in der gleichen Restklasse wie 44? ? :O das ganze ergibt doch eine riesengroße negative zahl
genau das gleiche Problem bei der nächsten Gleichung
nun muss ich die 42^23 mod 59 rechnen, also mit der anderen Primzahl, der einfachkeit halber nehmen wir die -17 weil sie in der gleichen Restklasse ist
aber die Gleichung dazu ergibt sich mir nicht.. kannst du mir die beiden Gleichungen erläutern?
Mit dem chinesischen Restsatz hätte ich dann
x ≡ -9 mod 53
x ≡ -3 mod 59
Dann bilde ich das Produkt der Module, 53 und 59, das wäre A = 3127.
A1 = 3127 / 53
A2 = 3127 / 59
Mit dem erweiterten euklidischen Algorithmus lassen sich nun Zahlen ri und si mit ri * ai + si * Ai = 1 finden
Muss ich nun den erweiterten euklidischen Algorithmus für 3127 und 53 und danach mit 3127 und 59 machen? denn der ggT ist ja in dem Fall immer entweder 53 oder 59 und ich weiß nicht ganz wie ich den dann anwende da diese Zahlen nicht teilerfremd sind :S wo ist mein denkfehler?