Prime Restklassengruppe

Die prime Restklassengruppe ist die Gruppe der primen Restklassen bezüglich eines Moduls ${\displaystyle n}$. Das ist zugleich die Gruppe der Einheiten des Restklassenrings ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ (die daher oft als ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ oder ${\displaystyle \mathbb {Z} _{n}^{*}}$ notiert wird). Denn die primen Restklassen sind genau die multiplikativ invertierbaren Elemente im Restklassenring. Die primen Restklassengruppen sind endliche abelsche Gruppen bezüglich der Multiplikation. Sie spielen in der Kryptographie eine bedeutende Rolle.

Die Gruppe besteht aus den Restklassen ${\displaystyle a+n\mathbb {Z} }$, deren Elemente zu ${\displaystyle n}$ teilerfremd sind. Gleichwertig dazu muss für den Repräsentanten ${\displaystyle a}$ der Restklasse ${\displaystyle \operatorname {ggT} (a,n)=1}$ gelten, wobei ggT den größten gemeinsamen Teiler bezeichnet. Darauf weist die Bezeichnung „prime Restklasse“ hin, für teilerfremd sagt man auch relativ prim. Die Gruppenordnung von ${\displaystyle \mathbb {Z} _{n}^{*}}$ ist durch den Wert ${\displaystyle \varphi (n)}$ der eulerschen φ-Funktion gegeben.