# Modulo-Rechnen, Zahlentheorie

Mathematik in wxMaxima www.mathematik-verstehen.de Haftendorn Okt 2010

Hilfen zum Handling
Achtung: Durch Anklicken der linken Zellmarkierung kann man die 
Abschnitte und auch einzelne Zellen aufklappen und auch wieder zuklappen.
Dazu Shift halten, dann werden auch alle Unterebenen aufgeklappt.
Endung *.wxmx ist komfortabel. Ist die Endung *.wxm muss man 
erst noch alle Ausgaben neu erzeugen. Mit Strg r  werden alle aufgeklappten Zellen ausgewertet.
Zum Lernen ist es besser die Zellen einzeln (mit Shift+Enter) auszuwerten.
Werte einzelne Zellen aus mit Shift-Enter. 
Auswertung in einem Rutsch: Falte alle Abschnitte auf,
werte alle Zellen mit Strg r aus ( auch Menu Cell Alle Zellen auswerten). 

Inhaltsverzeichnis

## Zahlen, Teilbakkeit, Vielfache

### Ganze Zahlen, Ganzzahlige Division

In der Zahlentheorie kommen nur die Ganzen Zahlen vor.
Dezimalzahlen spielen keine Rolle. 
Bei Divisionen interessiert man sich für den ganzzahlichen Anteil und den Rest. 

34/7; 
divide(34,7);

also 34 geteilt durch 7 ist 4 Ganze Rest 7 (wie in der Grundschule)

num(34/7);
denom(34/7);

Zähler (numerator) und Nenner (denominator) kann man aus 
Brüchen herausgreifen.

### Primfaktoren und Teiler

factor(731);
divisors(731);

factor(72);
ifactors(72);
divisors(72);

factor(123456789);

Die Zerlegung in Faktoren zeigt die Primfaktoren und ihre Potenzen.
Bei ifactors werden diese als Liste von Primahlen mit ihren Potenzen 
ausgegeben.  (integer =ganzzahlig)
Die Teiler einer Zahl sind alle Produkte, sich mit diesen Bausteinen
bilden lassen. Z.B. ist 3*3607 Teiler, aber auch 3^2*3803

3*3607; 3^2*3803;

divide(123456789,10821);  divide(123456789,34227);

Der Rest 0 war also vorherzusehen.

der Befehl divisors(n) zeigt die Teilemenge von n.

divisors(3607);

Die Zahlen, die nur sich und die 1 als Teiler haben, heißen Primzahlen.
3607 ist also eine Primzahl.  
Achtung: 1 ist keine Primzahl, das ist so definiert.

### Gemeinsame Teiler, ggT

divisors(72); divisors(48);

Der größte gemeinsame Teiler ist ersichtlich 24. 
Dafür gibt es den Begriff ggT(72,48) in Deutsch und in Eglisch
gcd(72,48)  greatest common divisor

gcd(72,48);

divisors(24);

In dieser Teilermenge sind tatsächlich alle gemeinsamen Elemente von 
den obigen beiden Teilermengen und 24 ist die größte unter ihnen.

Es gibt den Euklidischen Algorithmus auch in seiner erweiterten Form

gcdex(72,48);

gcdex(a,b) ist so zu lesen: [r,s,gcd] mit r*a+s*b=gcd(a,b)
Also hier

1*72+(-1)*48=24;

Diese "Vielfachsummendarstellung" wird in der Kryptografie sehr wichtig.
An passender Stelle wird dies aufgegriffen.
Achtung andere Software schreibt [gcd,r,s].

### Vielfache und Gemeinsame Vielfache

Die Vielfachenmengen sind naturgemäß unendlich groß. 
Hier nehmen wir 10 Elemente. Wir bleiben im Positiven, damit es übersichtlich bleibt.) 

Z:makelist(i,i,0,10);

Erstmal erzeugen wir und die Grundmenge Z   (eigentlich noch mit Negativen)

6*Z;

Das ist die abgekürzte Vielfachenmenge 6 Z als Liste.

8*Z;

Unter den gemeinsamen Elementen von 6Z und 8Z ist 24 das kleinste
kgV(6,8)=24 in Deutsch, in Englisch lcm(6,8) least common multiple

lcm(6,8);

## Die Gruppe Z(m) und das Modulo-Rechnen

### modulo - Begriff, Z(m)

Es kommt hier nur auf die Reste an, die beim ganzzahligen Teilen bleiben.
In mathematischer Schreibweise 34 mod 7 = 6 (lies 34 modulo 7 ist 6)

mod(34,7);

Nehmen wir von allen ganzen Zahlen immer nur den Rest modulo 7 
so erhalten wir offfenbar eine sehr kleine Menge, sie heißt Z(7)

Z;

mod(Z,7);
unique(mod(Z,7));

Jetzt nehmen wir negative Zahlen hinzu

ZZ:  makelist(i,i,-10,20);

mod(ZZ,7);
unique(mod(ZZ,7));

unique wirft die Doppelungen weg. Wir definieren also:

Z(m__):=unique(mod(ZZ,m__))$

Z(3); Z(7); Z(16);

### Rechnen in Z(m)

Mit den Zahlen dieser Menge kann man nun die Grundrechenarten 
+,-, *, hoch unbeschränkt ausführen, "geteilt" gehört nicht dazu.
Grundprinzip ist, dass man wie in ganzen Zahlen rechnet und alles modulo m
interpretiert.

11+13;
mod(11+13,16);

11-13;
mod(11-13,16);

Wenn man das selbst rechnen will, zählt man zu der -2 eine 16 hinzu, ist 14.
Oder man denkt 11=27 mod 16  und  27-13 =14

mod(11,16);  mod(27,16);

Man kann an jeder Stelle des Rechenvorgangs modulo m "herunternbrechen.
Das ist besonders interessant beim Potenzieren

mod(3^5,10);

selber: 3^2 =-1 mod 10 , 3^4=(3^2)^2=(-1)^2 mod 10 =1 mod 10; 
3^5=1*3 mod 10=3

3^5;

Da sieht man die 3 auch gleich als Rest beim Teilen durch 10.

### Multplikationstafeln von Z(m)

/*Definitionen, nach Auwertung wieder zuklappen */
plus(i,j,m):=mod(Z(m)[i]+Z(m)[j],m)$
maal(i,j,m):=mod(Z(m)[i]*Z(m)[j],m)$
plustafel(m):=block(
    array(ma,fixnum,m,m),
    for i:1 thru m do for j:1 thru m do ma[i,j]:plus(i,j,m),
    print("Plus-Tafel  modulo ",m),
    genmatrix(ma,m,m)
)$
maltafel(m):=block(
    array(ma,fixnum,m-1,m-1),
    for i:1 thru m-1 do for j:1 thru m-1 do ma[i,j]:maal(i+1,j+1,m),
    print("Mal-Tafel  modulo ",m),
    genmatrix(ma,m-1,m-1)
)$

m:6;Z(m);Z(m)[3];

plustafel(6);

maltafel(6);

for i:4 thru 11 do print(maltafel(i))$

### Zstern(m) die Gruppe der Teilerfremden

Teilerfremd zu m sind alle Zahlen i mit ggT(m,i)=1

/*Definitionen Zstern(m) und malsterntafel(m)*/
Zstern(m):=block([li],
    li:[],
    for i:1 thru m-1 do
        if gcd(m,i)=1 then li:endcons(i,li),
    return(li)
)$
malsterntafel(m):=block([le,Zs,malstern],
    Zs:Zstern(m), le:length(Zs),
    malstern(i,j,m):=(mod(Zs[i]*Zs[j],m)),
    array(ma,fixnum,le,le),    
    for i:1 thru le do for j:1 thru le do ma[i,j]:malstern(i,j,m),
    print("Malstern-Tafel  modulo ",m),
    genmatrix(ma,le,le)
)$

Zstern(20);

Für die Anzahl dieser Teilerfremden gibt es die Eulersche-Phi-Funktion

eulerphi(m):=length(Zstern(m))$
eulerphi(20);

malsterntafel(20);

for i:6 thru 21 do print(malsterntafel(i))$

### Potenztafeln

/* Definition potenztafel(m) */
potenztafel(m):=block([le,Zs,hochstern],
    Zs:Zstern(m), le:length(Zs),
    hochstern(i,j,m):=(mod(Zs[j]^i,m)),
    array(ma,fixnum,le,le),    
    for i:1 thru le do for j:1 thru le do ma[i,j]:hochstern(i,j,m),
    print("Potenz-Tafel von Zstern  modulo ",m),
    print("Zstern(",m,") hat ",le," Elemente"),
    genmatrix(ma,le,le)
)$

potenztafel(7);

for i:6 thru 21 do print(potenztafel(i))$

potenztafel(30);potenztafel(31);

## Ordnung eines Elementes, Powermod

### Ordnung

Wenn man sich die Potenztafeln ansieht, fällt auf, dass alle 
in der letzten Zeile ausschließlich 1 zeigen.
Das passt zu dem Satz der Gruppentheorie:
Element hoch Gruppenordnung =1
Die Gruppenordnung ist die Zahl der Elemente einer Gruppe.
Die Gruppen Zstern(m) haben eulerphi(m) Elemente

Zstern(10); eulerphi(10);

Zstern(16); eulerphi(16);

Man bildet den Begriff Ordnung eines Elementes:
ord(a)=k genau wenn k die kleinste Zahl mit a^k mod m =1 ist.
In den Potenztafeln ist k die Nummer der Zeile, in der zum ersten Mal
eine Eins in der k-Spalte auftaucht.

makelist(mod(7^i,16),i,1,8);

makelist(mod(5^i,16),i,1,8);

7 hat also in Zstern(16) die Ordnung 2, 5 hat die Ordnung 4

ordo(a,m):=block([p,z],
                    p:a,z:1, while p>1 do (p:mod(a*p,m), z:z+1),
                    return(z)
                   );

ordo(13,16);

makelist(mod(5^(4*n),16),n,1,10);

Man überlegt leicht, dass 5 hoch eine beliebiges 4-Vielfache 
modulo 16 gleich 1 ist. Darum kann man 5^2010 mod 16 im Kopf ausrechnen.
5^2010=5^(2008+2) mod 16 = 5^2 mod 16=25 mod 16=9

mod(5^2010,16);

Einweiter Satz der Gruppentheorie ist, dass dieElementordnung die 
Gruppenordnung teilen muss. (Begründung bei "Nebenklassen".
Also kommen nur die Teiler von eulerphi als Elementordnungen infrage.

potenztafel(18);

5 und 11 haben Ordnung 6, 7 und 13 haben Ordnung 3, 17 hat Ordnung2.

### Powermod

Für die Kryptografie ist es wichtig, dass hohe Potenzen 
riesiger Zahlen berechnet werden können.

/*Definition von pmod(a.k.m) powermod*/
pmod(a,k,m):=block([x,i,pot],
    i:k, x:1,pot:a,
    marke,
    if mod(i,2)=1 then (x:mod(x*pot,m),
        if i=1 then return(x),
        i:i-1    
    ),
    i:i/2,
    pot:mod(pot*pot,m),
    go(marke)
)$

pmod(5,3,16);mod(5^3,16);

pmod(12345,34567,16);mod(12345^34567,16);

Die letzte Rechnung könnte man mit einem gewöhnlichen Taschenrechner 
nicht ausführen. In der Kryptografie haben die Zahlen aber etwa 
200 Stellen und nicht 5 wie oben. Dann geht der rechte Befehl auch nicht mehr.

primlistebis(n):=([i,li],li:[],for i from 1  thru n do if  primep(i) then li:append(li,[i]),li);

lll:primlistebis(500);

primep(250348280129);

makelist(pmod(99,p-1,p),p, primlistebis(500));

mod(99^4998,4999);

### Nebenklassen

In einer Gruppe Zstern(m) kann es Elemente geben, deren Potenzen
schon die ganze Gruppe erzeugen, nämlich die Elemente mit maximaler Ordnung.

Zstern(18);

makelist(mod(5^i,18),i,1,6);

pl[13]:makelist(mod(13^i,18),i,1,3);

Die Elemente, die nicht in der Potenzenliste vorkommen, bilden
mit pl[13] echte Nebenklassen  g*pl[a]

mod(5*pl[13],18);mod(11*pl[13],18); mod(17*pl[13],18);

davon stimmen einige, hier sogar alle, überein.
Das Element der Ordnung 3 hat hier nur 2 Nebenklassen,
[13,7,1] und [5,11,17]
Alle Nebenklassen haben gleichviele Elemente, Anzahl ord(a) 
Darum teilt die Elementordnung die Gruppenordnung.

Eulerscher Satz für Gruppen: Die Elemenordnung teilt die Gruppenordnung

primep(250348280129);

pmod(2,340,341); factor(341);

## Betrachtungen für n=p q

### Definitionen

/*Definitionen, nach Auwertung wieder zuklappen */
plus(i,j,m):=mod(Z(m)[i]+Z(m)[j],m)$
maal(i,j,m):=mod(Z(m)[i]*Z(m)[j],m)$
plustafel(m):=block(
    array(ma,fixnum,m,m),
    for i:1 thru m do for j:1 thru m do ma[i,j]:plus(i,j,m),
    print("Plus-Tafel  modulo ",m),
    genmatrix(ma,m,m)
)$
maltafel(m):=block(
    array(ma,fixnum,m-1,m-1),
    for i:1 thru m-1 do for j:1 thru m-1 do ma[i,j]:maal(i+1,j+1,m),
    print("Mal-Tafel  modulo ",m),
    genmatrix(ma,m-1,m-1)
)$

tafel(p,q):=block(
    array(ma,fixnum,p,q),
    z:0,
    for i:1 thru p do for j:1 thru q do (z:z+1,ma[i,j]:z),
    print("Zahlen-Tafel bis ",p," mal ",q),
    genmatrix(ma,p,q)
)$

modptafel(p,q):=block(
    array(ma,fixnum,p,q),
    z:0,
    for i:1 thru p do for j:1 thru q do (z:z+1,ma[i,j]:mod(z,p)),
    print("ZahlenTafel modulo ",p),
    genmatrix(ma,p,q)
)$
modqtafel(p,q):=block(
    array(ma,fixnum,p,q),
    z:0,
    for i:1 thru p do for j:1 thru q do (z:z+1,ma[i,j]:mod(z,q)),
    print("ZahlenTafel modulo ",q),
    genmatrix(ma,p,q)
)$

### Tafeln

tafel(3,5);

p:3;q:5;tafel(p,q);modptafel(p,q); modqtafel(p,q);

p:5;q:7;tafel(p,q);modptafel(p,q); modqtafel(p,q);

p:11;q:13;tafel(p,q);modptafel(p,q); modqtafel(p,q);