Homepage - FAQ der Informatik.Ger - Modulo Inverses

FAQ der Informatik.Ger

Modulo Inverses

Wer kennt ein schnelles Verfahren, um die Gleichung a*x mod m = 1 zu lösen?

Die Holzhammermethode wäre: x = w^(phi(m)) mod m; mit phi(m) = Anzahl der zu m teilerfremden Zahlen aus [2,m-1]. Aber das wäre wohl etwas zu langsam.

Lösungsalgorithmus in C

Andernfalls bietet sich der alte EUKLID an. Die Gleichung ist genau dann lösbar, wenn w und m teilerfremd sind (GGT(w,m)=1). Das Berechnungsverfahren benutzt eine Abwandlung des EUDKLIDschen Algorithmus zur Lösung der linearen diophantischen Gleichunga*x + b*y = cHier ein C - Beispiel einschließlich einer Testschleife.
/*
Berechnung des Inversen von a im Modul m

Lösung der Gleichung
a*x mod m = 1, 0 < a < m , 0 < x < m
mittels des EUKLIDschen Algorithmus.
Falls a kein Inverses besitzt
(GGT(m,a)>1), wird 0 zurückgegeben.

H.Kraemer @ 2:2410/601.16     30.01.1988
*/

#include <stdio.h>

int inv(int m, int a) {
  int temp,q,flast=0,f=1,m0=m;

  while (a>1) {
    temp = m%a; q = m/a;
    m = a; a = temp;
    temp = f; f = flast-q*f; flast = temp;
  }
  return a==0 ? 0 : f>0 ? f : f+m0;
}

main() {
  int i,d,m=32749;  /* groesste Primzahl <= 32767 */
  /* Berechnung saemtlicher Inversen der primen
     Restklassengruppe von m */
  puts("");
  for (i=1;i < m;i++) {
    d=inv(m,i);
    if ( d != 0 && ((long)d*i)%m != 1 ) {
      puts("SHIT");break;
    }
  }
  return 0;
}

Falls der Modul m nicht prim ist, könnte man anhand der Primfaktorzerlegung von m unter günstigen Umständen noch etwas optimieren.

Eindeutigkeit

Selbstverständlich ist die Lösung einer solchen Kongruenz nicht eindeutig. Es gibt aber für jedes w, das mit m keinen gemeinsamen Teiler hat, genau ein repräsentatives x mit 1<=x<m, das die Gleichung löst und nach diesem ist in der Theorie der primen Restklassengruppen modulo m gefragt. Formal betrachtet, wirft man alle zueinander modulo m kongruenten Zahlen zu einem einzigen Objekt (Restklasse) zusammen, das man nach der einzigen Zahl z der Restklasse mit 0<=z<m benennt.

Nach Ersetzen der normalen Multiplikation durch die Restklassenmultiplikation sieht die Multiplikationstabelle der primen Restklassengruppe modulo 15 dann z.B. so aus:

* 1 2 4 7 8 11 13 14
1 1 2 4 7 8 11 13 14
2 2 4 8 14 1 7 11 13
4 4 8 1 13 2 14 7 11
7 7 14 13 4 11 2 1 8
8 8 1 2 11 4 13 14 7
11 11 7 14 2 13 1 8 4
13 13 11 7 1 14 8 4 2
14 14 13 11 8 7 4 2 1

Nach dieser Vereinbarung spricht man dann auch von der eindeutigen Lösung der Gleichung 7*x=1 in der primen Restklassengruppe modulo 15 oder noch kürzer vom Inversen von 7 modulo 15 (siehe Subject).

Von Horst Krämer @ 2:2410/601.16, 3.7.95/5.7.95

Valid HTML 4.01! Erstellt von Ralf Wiebicke, letzte Änderung 01.02.97