Restklassenring: inverses multiplikatives Element
-
Hallo.
Ich habe einen Restklassenring modulo M und eine Zahl x aus dem Ring.
Es ist sichergestellt, dass M nicht von x geteilt wird.
Wie kann ich nun das inverse multiplikative Element von x möglichst schnell bestimmen?
Also wie bestimmte ich effizient ein y, so dass x * y = 1 (modulo M) ist?
Bisher habe ich immer alle y ausprobiert. Geht es schneller?
Danke schonmal.
-
Ich würde es so machen: (M+1)/x=:y und dann y mit einer natürlichen Zahl n multiplizieren, so dass n*y eine natürliche Zahl ist und dann n*y MOD M rechnen und das Ergebnis sollte das multiplikative Inverse im Ring sein.
-
Eine relativ schnelle Methode ist der erweiterte euklidische Algorithmus.
Dass x nicht M teilt und 0 < x < M bedeutet, dass ggT(x, M) = 1. Dann liefert dir der erweiterte euklidische Algorithmus ganze Zahlen y, z fuer die x*y + M*z = 1 gilt. Nimm diese Gleichung modulo M und du bekommst x*y = 1 (mod M), das y aus dem erweiterten euklidischen Algorithmus ist also deine Loesung.