Prime Restklassengruppe
aus Wikipedia, der freien Enzyklopädie
Die prime Restklassengruppe ist die Gruppe der primen Restklassen 
. Sie wird mit 
oder 
symbolisiert. Hierbei steht mod wie üblich für den Modulo-Operator.
Da die Menge aller primen Restklassen eine endliche abelsche Gruppe bezüglich der Multiplikation bildet, spielen sie in der Kryptografie eine bedeutende Rolle.
Die Struktur von 
ist bekannt; bezeichnet vp(n) die p-Bewertung von n, ist also
die Primfaktorzerlegung von n, so gilt nach dem chinesischen Restsatz
[Bearbeiten] Berechnung der Inversen Elemente
Zu jeder primen Restklasse 
existiert eine prime Restklasse 
, sodass gilt:
Die prime Restklassengruppe ist also das inverse Element zu bezüglich der Multiplikation in der primen Restklassengruppe . Ein Repräsentant von lässt sich mit Hilfe des Erweiterten Euklidischen Algorithmus bestimmen. Indem man die obige Kongruenz umschreibt zu
- ab + km = 1
sieht man, dass der Erweiterte Euklidische Algorithmus auf a und m angewand mit b einen Repräsentanten von berechnet.
