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
Die Zahlentheorie bildet mit die Grundlage vieler moderner Verfahren im Umfeld der Kryptologie:
Primzahlen und zyklische Gruppen
Ist p eine Primzahl, so bildet
D.h. zunächst ist es eine Gruppe mit p-1 Elementen:
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, a2,a3,...ar
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, a2, 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 2k mod(5) darstellen.
21mod(5) = 2 | 22mod(5) = 4 | 23mod(5) = 3 | 24mod(5) = 1 |
2. Für {1,2,3,4,5,6} erzeugen 3k mod(7) und 5k mod(7) alle Elemente.
31mod(7) = 3 | 32mod(7) = 2 | 33mod(7) = 6 | 34mod(7) = 4 | 35mod(7) = 5 | 36mod(7) = 1 |
51mod(7) = 5 | 52mod(7) = 4 | 53mod(7) = 6 | 54mod(7) = 2 | 55mod(7) = 3 | 56mod(7) = 1 |
3. Für {1,2,3,4,5,6,7,8,9,10} erzeugen ak mod(11) a=2,6,7,8 alle Elemente.
21mod(11) = 2 | 22mod(11) = 4 | 23mod(11) = 8 | 24mod(11) = 5 | 25mod(11) = 10 | 26mod(11) = 9 | 27mod(11) = 7 | 28mod(11) = 3 | 29mod(11) = 6 | 210mod(11) = 1 |
61mod(11) = 6 | 62mod(11) = 3 | 63mod(11) = 7 | 64mod(11) = 9 | 65mod(11) = 10 | 66mod(11) = 5 | 67mod(11) = 8 | 68mod(11) = 4 | 69mod(11) = 2 | 610mod(11) = 1 |
71mod(11) = 7 | 72mod(11) = 5 | 73mod(11) = 2 | 74mod(11) = 3 | 75mod(11) = 10 | 76mod(11) = 4 | 77mod(11) = 6 | 78mod(11) = 9 | 79mod(11) = 8 | 710mod(11) = 1 |
81mod(11) = 8 | 82mod(11) = 9 | 83mod(11) = 6 | 84mod(11) = 4 | 85mod(11) = 10 | 86mod(11) = 3 | 87mod(11) = 2 | 88mod(11) = 5 | 89mod(11) = 7 | 810mod(11) = 1 |
Betrachtet man auch die anderen Basiszahlen,
so erkennt man, daß dadurch Untergruppen entstehen:
so erzeugt die 4 mod(5) die Untergruppe {1,4}
p=5 | 2 | 4 | 3 | 1 |
3 | 4 | 2 | 1 | |
(1,4) | 4 | 1 |
oder die 2 und die 4 mod(7) die Untergruppe {1,2,4}
sowie die 6 mod(7) die Untergruppe {1,6}
p=7 | 2 | 4 | 1 | |||
3 | 2 | 6 | 4 | 5 | 1 | |
(1,2,4) | 4 | 2 | 1 | |||
5 | 4 | 6 | 2 | 3 | 1 | |
(1,6) | 6 | 1 |
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}
p=11 | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | 6 | 1 |
(1,3,4,5,9) | 3 | 9 | 5 | 4 | 1 | |||||
(1,3,4,5,9) | 4 | 5 | 9 | 3 | 1 | |||||
(1,3,4,5,9) | 5 | 3 | 4 | 9 | 1 | |||||
6 | 3 | 7 | 9 | 10 | 5 | 8 | 4 | 2 | 1 | |
7 | 5 | 2 | 3 | 10 | 4 | 6 | 9 | 8 | 1 | |
8 | 9 | 6 | 4 | 10 | 3 | 2 | 5 | 7 | 1 | |
(1,3,4,5,9) | 9 | 4 | 3 | 5 | 1 | |||||
(1,10) | 10 | 1 |
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:
ar-s=1
Damit bilden a, a2, a3, ..aq=1 eine Untergruppe, womit q ein Teiler von p-1 ist.
also q*c=p-1 für eine natürliche Zahl c.
Da aq=1 gilt: (aq)c=1 also
aq*c=ap-1 = 1
also gilt der kleine Satz von Fermat.