Die Gesetzmäßigkeiten der ganzen Zahlen, speziell die Aussagen über Teilbarkeit, Primzahlen und die Betrachtung von Restklassen bei der Division, wurden nach Einzelergebnissen im Altertum durch

• Euklid (300 vor Chr.) erst relativ spät, unter anderem durch die Mathematiker
• Pierre Fermat (1601 - 1666),
• Leonhard Euler (1707 - 1783) und
• Ernst Carl Friedrich Gauss (1777 - 1855)

Die Zahlentheorie bildet mit die Grundlage vieler moderner Verfahren im Umfeld der Kryptologie:

• Generierung von Pseudozufallsfolgen
• diverse Verschlüsselungsverfahren
• Digitale Unterschrift
• elektronisches Geld
• und viele weitere Verfahren

Primzahlen und zyklische Gruppen

Ist p eine Primzahl, so bildet

{1,2,3,...,p-1} mit der Multiplikation mod(p)

D.h. zunächst ist es eine Gruppe mit p-1 Elementen:

• zu je zwei Zahlen a und b aus M={1,2,3,..,p-1}
  gibt es eine eindeutige Zahl c aus M
  mit c = a * b mod (p).

• Es gibt ein neutrales Element 1 aus M, so daß
  a * 1 mod (p) = 1 * a mod(p) = a für alle a aus M.

• Es gilt (a * b mod(p)) * c mod (p) = a * (b * c mod(p))mod(p)

• Zu jedem a aus M gibt es ein Inverses a^-1 aus M
  mit a * a^-1 mod(p) = 1.

Neben der Gruppeneigenschaft, lassen sich alle Elemente 1,2,3,...,p-1 als
Ergebnis der Potenz mindestens eines Elementes a aus M erzeugen.

D.h. es gibt ein a aus M, so daß a, a²,a³,...a^r alle Elemente
aus {1,2,3,..,p-1} ergeben.

Nicht jedes a aus M erzeugt dabei M.
Aber für ein beliebiges a aus M
bilden die Potenten a, a², usw. zumindest eine Teilmenge
aus {1,2,3,...,p-1}, die selbst eine zyklische Gruppe darstellen.

1. Alle Elemente von {1,2,3,4} lasssen sich als Potenzen von 2^k mod(5) darstellen.

2. Für {1,2,3,4,5,6} erzeugen 3^k mod(7) und 5^k mod(7) alle Elemente.

3. Für {1,2,3,4,5,6,7,8,9,10} erzeugen a^k mod(11) a=2,6,7,8 alle Elemente.

Betrachtet man auch die anderen Basiszahlen,
so erkennt man, daß dadurch Untergruppen entstehen:

so erzeugt die 4 mod(5) die Untergruppe {1,4}

oder die 2 und die 4 mod(7) die Untergruppe {1,2,4}
sowie die 6 mod(7) die Untergruppe {1,6}

und schließlich

die 3,4,5 und 9 mod(11) die Untergruppe {1,3,4,5,9}
sowie die 10 mod (11) die Untergruppe {1,10}

Allgemein gilt für die Ordnung einer solchen Untergruppe,
daß sie ein Teiler der Ordnung der Gruppe ist (Satz von Lagrange).

In den Beispielen gilt:

p=5  => Ordnung {1,2,3,4}=4        Ordnung {1,4}=2 mit 2 Teiler von 4.
p=7  => Ordnung {1,2,3,4,5,6}=6  Ordnung {1,2,4}=3      Ordnung {1,6}= 2
p=11=> Ordnung Gruppe = 10       Ordnung {1,3,4,5,9}=5 Ordnung {1,10)=2

Mit p als Primzahl ist p-1 die Ordnung der zyklischen Gruppe und für ein beliebiges a aus {1,2,3,...,p-1} gilt:

Wenn a, a², a³, ..a^r-1 verschieden
und ergibt sich nach r-Schritten das bereits vorhandene Element a^s
a^r=a^s mit s < r

(Da es nur maximal p-1 Elemente als Ergebnisse gibt, muß sich
spätestens nach p Schritten ein Element wiederholen)

so gilt nach Multiplikation mit a^-s

a^r-s=1

Damit bilden a, a², a³, ..a^q=1 eine Untergruppe, womit q ein Teiler von p-1 ist.

also q*c=p-1 für eine natürliche Zahl c.

Da a^q=1 gilt: (a^q)c=1 also

a^q*c=a^p-1 = 1

also gilt der kleine Satz von Fermat.