Zurück zur Übersichtstabelle
Das ist ein Programm zum Lösen von Kongruenzen

Beispiel : X · 134 = 109 (mod 227)

Um diese Gleichung zu lösen brauchen wir Primitivwurzeln in dem (primen) Restklassenkörper Z/p

Mit deren Hilfe können wir dann einfach die multiplikativ, inversen Elemente berechnen.
Somit können dann die Kongruenzen gelöst werden.

Anwendug von Kongruenzen in der Praxis
Beim RSA-Verfahren muss der Empfänger die Kongruenz E ·D = 1 (mod M) lösen, um sich den geheimen Schlüssel D zu berechnen.
Leider ist dort M kein Primzahlmodul, so dass es nicht mittels Primitivwurzeln lösbar ist


Hier nun die Primitivwurzel-Berechnug
Eingabe von M und E Berechnungen
Primer Zahlen Modul M  
(das entspricht der Hilfszahl M beim RSA Verfahren)
Element E


  		Anzahl Primitiv-wurzeln    ( Das entpricht der Anzahl der teilerfremden Elementen von (m-1) ) 
Ordnung von Z/M  

hoch = (mod )
 Die Ordnung von E ist bezüglich der gewählten PW :

Probe : E · E-1 = 1 (mod M)

· = 1 (mod )
 Das Inverses Element zu E ist 
(Das entspricht dem geheimen Schlüssel D ) 

Die Lösung der obigen Kongruenz ist somit :
X = 109 · 144 = 33 (mod 227)