Prof. Dr. W. Conen, FH Gelsenkirchen, Version 1.21 LDS – Exkurs: Rechnen… Prof. Dr. Wolfram...

Prof. Dr. W. Conen, FH Gelsenkirchen, Version 1.2

1

LDS – Exkurs: Rechnen…

Prof. Dr. Wolfram ConenVersion 1.2


2

Schauen Sie sich um…

Computer und Netzwerke sind überall!

Sie ermöglichen ein feingesponnenes Geflecht komplexer menschlicher Aktivitäten: Erziehung, Geschäftsleben, Unterhaltung, Forschung, Produktion,

Gesundheitsmanagement, menschliche Kommunikation, selbst Kriegsführung

Es gibt zwei wichtige technologische Grundlagen dieser faszinierenden Entwicklung: Die offensichtlichere: die atemberaubende Geschwindigkeit, mit der uns

Fortschritte in Mikroelektronik und Chip-Design immer schnellere Hardware bringen

Die „verstecktere“ Grundlage: Eine intellektuelle Unternehmung, die einen wesentliche Treibstoff für die fortschreitende Computer-Revolution bietet: Die Suche nach effizienten Algorithmen

It‘s a fascinating story. Gather ‚round and listen close.[Sanjoy Dasgupta, Christos Papadimitriou und Umesh Vazirani in „Algorithms“,

1.ed, McGraw-Hill, 2008]


3

Schauen Sie sich um…

Die Suche nach effizienten Algorithmen

… wird Thema in ADS…aber auch in LDS werden wir schon (mathematisch motivierte) Ausflüge dorthin unternehmen…zum Beispiel im folgenden.

Wir werden uns mit Zahlen beschäftigen und rechnen lernen

… und mit Hilfe von Primzahlen unseren Freunden (ziemlich) sichere Emails senden

Und natürlich werden wir das so genau anschauen, dass sie selbst „per Hand“ verschlüsseln können werden!


4

Algorithmen mit Zahlen

Im folgenden werden zwei sehr alte Probleme eine zentrale Rolle spielen:

Faktorisierung: Gegeben sei eine Zahl N, stelle sie dar als Produkt ihrer Primfaktoren

Prüfen der Primzahleigenschaft: Gegeben sei eine Zahl N, bestimme, ob sie eine Primzahl ist

Faktorisierung ist ein „hartes“ Problem: der schnellste bisher bekannte Algorithmus benötigt einen Zeitaufwand, der exponentiell ist zur Zahl der Bits, die N kodieren.

Zum Testen der Primzahleigenschaft existiert hingegen ein effizienter Algorithmus (ausführbar mit einem Zeitaufwand, der sich durch ein Polynom abschätzen läßt)

Aber mehr dazu später.


5


Eine elementare Eigenschaft von Dezimalzahlen:

Die Summe von drei beliebigen einstelligen Zahlen ist höchsten zweistellig.

Prüfen wir das: Die größte einstellige Zahl ist 9 9+9+9 = 27, die Aussage stimmt also offensichtlich

Diese Aussage gilt für Zahlen zu jeder Basis b >= 2

Deshalb können wir beim Addieren zweier Zahlen, egal, wie sie repräsentiert sind, diese immer rechtsbündig untereinander schreiben und dann von rechts nach links ziffernweise addieren und einen (immer) EINSTELLIGEN Übertrag (0 ist auch erlaubt)mitführen, der beim nächsten Durchgang hinzu addiert wird (und wieder nur zu einem einstelligen Übertrag beiträgt, s. unsere Aussage oben).


6


Aber was war noch mal eine Basis b?

Dezimalzahlen, z.B. 234, lassen sich wie folgt als Summe von Potenzen zur Basis 10 darstellen: 234 = 4*100 + 3*101 + 2*102

Zur Erinnerung: x0 ist immer 1, x1 ist immer x, also gilt auch für x=10: 101 = 10 102 = 10*10 = 100 10y = 10…0 = 1 mit genau y Nullen, y >= 0

Die Zahl, die durch 234 im Dezimalsystem repräsentiert wird, lässt sich aber auch zu anderen Basen darstellen


7


234 im Dezimalsystem ist… 14*161 + 10*160 = EA im Hexadezimalsystem

Basis 16, klar. Dann braucht man aber auch 16 Ziffern… …also nimmt man noch A (für 10), B (11), C(12), D(13), E (14), F (15),

hinzu Das Hexadezimalsystem wird ihnen noch oft begegnen, weil die

„Wortbreite“ in Computersystemen regelmäßig durch 8 teilbar ist (früher 8 Bit, später 16, dann 32, heute oft 64) – und in 8 Bit genau 256, also 16*16, Werte passen – genauer: die Zahlen von 0 bis 255, oder, Hexadezimal, von 00 bis FF (FF = 15*161 + 15 = 255)


8


234 im Dezimalsystem ist…

192 + 40 + 2 = 3*82 + 5*81 + 2*80 = 352 im Oktalsystem

Basis? Klar, 8

Von Dieben im Mittelalter erfunden, weil denen regelmässig beide Daumen abgehackt wurden (zur Strafe…)

Auch praktisch, wenn die Wortbreite nur bei 3 Bit (bzw. 6) liegt

Denn dann kann man nur die Werte 0..7 kodieren (bei 6-Bit wird man dann zweistellig 00..77)

Und das sind genau die Ziffern im Oktalsystem


9


Was meint denn „Wortbreite“? Rechts ist der Speicher ihres

Computers Die einzelnen „Speicherzellen“

lassen sich einzeln adressieren Hier z.B. 0, 1, 2, 3 Und die „Breite“ der Zelle meint

die „Wortbreite“ (des Speichers), hier wird die Zahl der „Bits“ gezählt, die in eine Zelle passen

Der Prozessor kann intern sogar eine andere Breite haben, als der Speicher

0111001100010011

0111001110010011

0111001100010000

0111001100011111

0:

1:

2:

3:


10


Und was sind „Bits“? Das sind die „kleinsten“

Informationseinheiten im Rechner, sie sind „an“ oder „aus“, „wahr“ oder „falsch“, 1 oder 0

Mit Bits kann man unsere Zahl 234 auch darstellen – in der sogenannten Binärdarstellung (binär = zweiwertig):

23410 = 111010102

Wie kommt man drauf?

0111001100010011

0111001110010011

0111001100010000

0111001100011111

0:

1:

2:

3:


11


234 = 128 + 64 + 32 + 8 + 2 = 1*27 + 1*26 + 1*25 + 0*24 + 1*23 + 0*22 + 1*21 + 0*20

= 11101010 binär Mit 8 Bit kann man also wieviele Zahlen repräsentieren? Genau: Bei jedem Bit kann man sich zwischen 0 und 1 entscheiden, mit

einem Bit hat man also 2 Wahlmöglichkeiten… … mit zwei Bits kommen noch mal jeweils zwei Möglichkeiten hinzu, also

insgesamt 2*2 = 4, usw. … bei 8 Bit sind es dann: 2*2*2*2*2*2*2*2 = 28 = 256 Wieviel sind es bei 16 Bit? Wieviel bei 32? Wieviel bei 64? 65.536, 4.294.967.296, viele… (ca. 1,844674407371 * 1019)


12


Die Frage nach den Wahlmöglichkeiten als Entscheidungsbaum – aber nur für 3 Bit…

Sie müssen drei Fragen mit „Ja“ oder „Nein“ beantworten, wieviele mögliche Kombinationen von Antworten gibt es?

Ja (=1) Nein (=0)

1 1

1111 0 0 0 0

00

111

Erste Frage: Sind sie reich?

Zweite: Sind sie schlau?

Dritte: Sind sie schön?

110

101

100

011

010

001

000 8 = 23

Innere Knoten

Blätter


13


Auf der ersten Ebene (engl. Level) sind 20 Knoten, auf der zweiten doppelt so viele, also 21, auf der dritten wieder doppelt so viele, also 22, und auf der vierten Ebene 23 ... auf der n-ten Ebene sind also 2n-1 Knoten.

Das gilt IMMER für vollständige Binärbäume (vollständig meint: jede Ebene ist vollständig besetzt).

Vorsicht übrigens: oft spricht man auch von einer „Tiefe“ oder „Höhe“ eines Baumes, und die zählt man meist ab 0 (unser Baum hätte dann die Tiefe 3 gehabt) und der oberste Knoten, die sogenannte Wurzel, wäre auf Tiefe 0 gewesen.

Wieviele Knoten hat ein vollständiger Binärbaum insgesamt? Anzahl Knoten = Anzahl innere Knoten + Anzahl Blätter =

(1 + 2 + 4) + 8 = (23 – 1) + 23 = 24 – 1 = 16 – 1 = 15 Allgemein für vollständige Binärbäume mit Höhe h also: 2h+1 - 1


14


Wie findet man die binäre Darstellung einer Dezimalzahl? Nehmen wir das Beispiel 234. Was suchen wir? Wir suchen eine Darstellung der Zahl 234 als SUMME

VON ZWEIERPOTENZEN Formal: wir suchen nach Zahlen x0, x1, x2, ... mit

234 = x0* 20 + x1* 21 + x2* 22 + ...

unter den Nebenbedingungen: xi aus {0,1} Erste Beobachtung: es gibt eine „kleinste“ Zweierpotenz 2k, für die gilt

2k <= 234 < 2k+1

Hier ist das für 27 = 128 (denn 128 = 27 <= 234 < 28 = 256) Ab k sind also alle weiteren Koeffizienten xk+1, xk+2, ... gleich 0 zu setzen.


15


Wie findet man die binäre Darstellung einer Dezimalzahl? Wir haben jetzt also einen Koeffizienten gefunden, nämlich x7 = 1, denn 128

ist EINMAL in 234 enthalten. Damit können wir unsere Suche eingrenzen:

wir suchen nach Zahlen x0, x1, x2, x3, x4, x5, x6 mit

234 = x0* 20 + x1* 21 + x2* 22 + x3* 23 + x4* 24 + x5* 25 + x6* 26 + 1 * 27

unter den Nebenbedingungen: xi aus {0,1} Jetzt wenden wir unsere erste Beobachtung auf 234 – 27= 234 – 128 = 106 an:

es gilt 64 = 26 <= 106 < 27 = 128, also ist x6 = 1. Ebenso ist dann x5 = 1, denn 32 = 25 <= 106 – 64 (= 42) < 64 = 26

x4 ist hingegen 0 (denn 24 = 16 > 10), aber x3 = 1 (mit 23 <= 10 < 24) x2 ist wieder 0 (denn 22 = 4 > 2), x1= 1 (mit 21 = 2), und x0 dann wieder 0.


16


Wie findet man die binäre Darstellung einer Dezimalzahl? Insgesamt ergibt sich also

234 = 0 * 20 + 1 * 21 + 0* 22 + 1 * 23 + 0* 24 + 1* 25 + 1* 26 + 1 * 27 = 2 + 8 + 32 + 64 + 128 = 128 + 64 + 32 + 8 + 2 = 27 + 26 + 25 + 23 + 21

234 ist in Binärdarstellung also

11101010, das entspricht den Koeffizienten x7 x6 x5 x4 x3 x2 x1 x0

(Achtung, wir betrachten nur positive Zahlen!)


17


Wie findet man die binäre Darstellung einer Dezimalzahl? Etwas sehr Ähnliches als Algorithmus („Holzhammer-Methode“):

INPUT: Gegeben eine natürliche Zahl n ein DezimaldarstellungOUTPUT: Die Zahl n in Binärdarstellung1. Suche die „kleinste“ Zweierpotenz 2k, für die gilt 2k <= n < 2k+1

2. Halte dieses k fest. Merke dir: xk = 1. Setze n‘ = n - 2k

3. Laufe von i = k-1 bis i = 0. 1. Prüfe, ob n‘ < 2i.

Falls JA, setze xi = 0, sonst setze xi = 1 und n‘ = n‘-2i

4. Gib xk xk-1 xk-2 ... x0 aus. Für 234 würden wir also zuerst 2i und damit k=7 finden und dann alle

kleineren Zweierpotenzen „von groß nach klein“ prüfen, ob sie im Rest enthalten sind (und gegebenenfalls den Rest verkleinern)


18

Einige Zweierpotenzen

20 21 22 23 24 25 26 27

1 2 4 8 16 32 64 128

28 29 210 211 212 213 214 215

256 512 1024 2048 4096 8192 16384 32768

216 217 218 219 220 221 222 223

65536 131072 262144 524288 1048576 2097152 4194304 8388608

Wenden Sie den Algo bitte für 888 an (Hinweis: idealerweisekönnen sie die folgende Tabelle auswendig)


19


Eingabe: n = 888 Schritt 1: 2k = 29 = 512 Schritt 2: k = 9, x9 = 1, n‘ = 888 – 512 = 376 Schritt 3 (Schleife), siehe rechts: Schritt 4, Ausgabe:

1101111000

i 2i xi n‘ neu

8 256 1 120

7 128 0 -

6 64 1 56

5 32 1 24

4 16 1 8

3 8 1 0

2 4 0 -

1 2 0 -

0 1 0 -


20


Im Algorithmus fand sich die folgende Zeile:1. Suche die „kleinste“ Zweierpotenz 2k, für die gilt 2k <= n < 2k+1

Das könnte man auch in der Schleife wiederholt ausführen (für neue n‘) – und die xi zwischen den gefundenen ks 0 setzen.

Dann hätte man eine Variante des Algorithmus, die genauer unserer ursprünglichen Beschreibung entspricht (aber etwas komplizierter aufzuschreiben wäre)

Uns interessiert aber jetzt: wie finden wir den diese Zweierpotenz? z.B. durch SUCHE (dazu werden wir noch einiges hören) ...oder durch Anwenden des Zweierlogarithmus: log2 x ist die Zahl mit

der man 2 potenzieren muss, um x zu erhalten. Wenn wir von dieser Zahl die Nachkommastellen abschneiden, haben wir unser k.

Beispiel: log2 888 = 9,7944158663501, Nachkomma abschneiden: 9 Aber: auch das muss man erstmal berechnen!!


21


Eine weitere Option ist es, die Zahl fortgesetzt durch 2 zu teilen, bis man die größte Zweierpotenz gefunden hat und so das k zu bestimmen.

Machen wir das einmal für 234: 234 / 2 = 117 117 / 2 = 58 Rest 1 58 / 2 = 29 29 / 2 = 14 Rest 1 14 / 2 = 7 7 / 2 = 3 Rest 1 3 / 2 = 1 Rest 1 1 / 2 = 0 Rest 1 Wir können also 234 7mal erfolgreich durch 2 teilen und behalten ab und an einen

Rest zurück – d.h. 27 ist in 234 enthalten, aber nicht 28. Und weiter? Jetzt könnten wir 27 von 234 abziehen und wieder fortgesetzt durch 2

teilen…usw., wie im (modifizierten) Algorithmus vorgeschlagen.


22


Aber ... das ist gar nicht nötig, denn wir haben einen weiteren Algorithmus „entdeckt“, mit dem wir die Binärrepräsentation bestimmen können.

234 / 2 = 117 234 lässt sich glatt durch 2 teilen, also ist 20 = 1nicht als Faktor in der Binärrepräsentation von 234enthalten. 21 = 2 ist 117mal in 234 enthalten.

117 / 2 = 58 Rest 1 117 lässt sich nicht glatt durch 2 teilen (also lässt sich 234 nicht glatt durch 4 teilen), also ist 21 = 2 als Faktor enthalten.

58 / 2 = 29 58 lässt sich glatt durch 2 teilen (also lässt sich 232 glatt

durch 8 teilen), also ist 22 nicht als Faktor enthalten. 29 / 2 = 14 Rest 1 29 lässt sich nicht glatt durch 2 teilen (also lässt sich

232 nicht glatt durch 16 teilen), also ist 23 = 8 alsFaktor enthalten.

s. nächste Folie


23


14 / 2 = 7 14 lässt sich glatt durch 2 teilen (also lässt sich 224 glatt durch 32 teilen), also ist 24 = 16 nichtenthalten.

7 / 2 = 3 Rest 1 7 lässt sich nicht glatt teilen (also lässt sich 224nicht glatt durch 64 teilen), also ist 25 = 32

enthalten. 3 / 2 = 1 Rest 1 3 lässt sich nicht glatt teilen (also lässt sich 192

nicht glatt duch 128 teilen), also ist 26 = 64enthalten.

1 / 2 = 0 Rest 1 1 lässt sich nicht glatt teilen (also lässt sich 128 nicht glatt durch 256 teilen), also ist 27 = 128enthalten.

Fertig! Wir haben die Repräsentation gefunden: 11101010 das sind genau die Reste, die wir beim Teilen durch 2 gefunden haben, der

oberste Rest steht ganz rechts usw. Auch das ergibt wieder einen Algorithmus (ohne Suche und Logarithmen, nur

elementares Teilen durch 2!).


24


Hier noch eine Erklärung für den Algorithmus des fortgesetzten Teilens, den wir gerade kennengelernt haben.

Wenn wir 11101010 fortgesetzt jeweils eine Stelle nach rechts schieben (shiften) würden, würden rechts genau die Reste herausfallen, die wir gerade bestimmt hatten (auch in der gleichen Reihenfolge).

Das ist aber auch keine Überraschung: Das Anhängen einer 0 an eine Binärzahl (Links-Shift) entspricht dem Multiplizieren mit 2, das Shiften nach rechts entspricht dem Teilen durch 2 (und die herausfallende Zahl bringt den Rest) – eben das, was wir gerade gemacht haben.

Noch ein kleiner Hinweis: in fast allen Programmiersprachen gibt es die Shiftoperation, die man dort auch auf ganze Zahlen anwenden kann, z.B. auf 234. So kann man auch die Binärrepräsentation von 234 erzeugen (kleines Problem: wann Aufhören mit dem Shiften? Wortbreite! Und wie die gleich herausfallende Stelle herausfinden – oft wird nur das Shiftergebnis zurückgeliefert, nicht die herausgeschobene Stelle? Prüfen, ob rechtes Bit gesetzt ist, z.B. durch Ver-Unden mit einer 1)

Der Rechner teilt übrigens nicht durch 2, sondern shiftet einfach die interne Binärrepräsentation der Zahl, die er ja ohnehin „vorhält“.


25


Addition, s. oben: Deshalb können wir beim Addieren zweier Zahlen, egal, wie sie repräsentiert

sind, diese immer rechtsbündig untereinander schreiben und dann von rechts nach links ziffernweise addieren und einen (immer) EINSTELLIGEN Übertrag (0 ist auch erlaubt)mitführen, der beim nächsten Durchgang hinzu addiert wird…

1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 (Additionsregeln) + 1 1 0 1 0 1 1 1 0 0 1 1 0 0 1 1 Ü 1 1 1 1 1 1 1 - - 0 1 0 1 0 1 0 1

---------------------- -------------------------------- = 1 1 0 0 0 0 0 0 1 00 01 01 10 01 10 10 11

Die 8 binären Rechenregeln für Addition.Die erste Stelle wird in die Übertragszeileeingetragen, die zweite in die Ergebniszeile.


26

Multiplikation

1 1 0 1 (=13 dezimal) * 1 0 1 1 (=11 dezimal)

---------------------- 1 1 0 1 (1101 mal 1, kein Shift)

1 1 0 1 (1101 mal 1, 1 Links-Shift) 0 0 0 0 (1101 mal 0, 2 Links-Shift)

1 1 0 1 (1101 mal 1, 3 Links-Shift) ---------------------- 1 0 0 0 1 1 1 1 (=143 dezimal)

Ungefähre Kosten: Wenn beide Zahlen n Bits lang sind, dann entstehen n Zwischenreihen mit einer Länge bis zu 2n Bits. Wenn wir jetzt zwei Zeilen addieren und dann das Zwischenergebnis zur nächsten Zeile addieren, dann haben wir „ungefähr“ n-1 mal O(n) Bits zu addieren, in Summe O(n2). Zum O-Kalkül: siehe 2. Semester, theoretische Informatik / ADS.


27

Multiplikation einmal anders

Eine Methode, die bereits Al Kwarizmi (der Namensgeber für den Begriff „Algorithmus“) im 9. Jahrhundert nach Christi kannte und in einem Buch veröffentlichte:

Um zwei Dezimalzahlen x und y zu multiplizieren, schreibe sie zunächst direkt nebeneinander. Wiederhole dann das folgende: Teile die erste Zahl durch 2, runde das

Ergebnis ab (abschneiden der Nachkommastelle ,5) und verdopple die zweite Zahl fortlaufend.

Tue dies, bis die erste Zahl zur 1 wurde. Streiche dann alle Zeilen, in denen die erste

Zahl gerade (=even) war und addiere die übrigen Zeilen auf.

11 * 135 262 521 104---------- 143


28


11 * 13 | 1 5 26 | 12 52 | 0 1 104 | 1------------- 143

1 0 1 1 * 1 1 0 1 =

1 1 0 1 (=13) 1 1 0 1 (=26) 0 0 0 0 1 1 0 1 (=104)

---------------------- 1 0 0 0 1 1 1 1 (=143)

Hier simulieren wir also die „normale“ Multiplikation, allerdings, ohne die Binärrepräsentation der 11 zu kennen (die erzeugen wir aber nebenbei „von rechts nach links“)


29


y x11 * 13 5 26 2 52 1 104 ---------- 143

Multiplikationsregel für zwei ganze Zahlen x und y, y >=0:

2(x * xy/2y), falls y gerade x*y = {x + 2(x * xy/2y), falls y ungerade 0 , falls y = 0

Hier schneidet xy/2y die Nachkommastelle von y/2 ab Man nennt das die floor-Funktion; ceiling gibt es

auch, es rundet nach oben auf die nächstgrößere ganze Zahl auf, allerdings nicht, wenn die Ausgangszahl schon ganzzahlig ist.


30

Multiplikation als Pseudo-Code

function multiply(x,y) Input: Zwei ganze n-Bit Zahlen x,y mit y >= 0

Output: Das Produkt der Eingabezahlen if y=0: return 0 z = multiply(x, xy/2y) if y is even (gerade):

return 2z else:

return x + 2z

Beispielausführung s. Übung Aufwand ist übrigens wieder O(n2)


31

Division

Was bedeutet es, eine nicht-negative ganze Zahl x durch eine positive ganze Zahl y, y 0, zu dividieren?

Gesucht ist ein Quotient q und ein Rest r, so dass: x = y*q + r Nebenbedingung: 0 <= r < y

Beispiel: 17 / 5 = 2*5 + 7? Falsch: r > y 17 / 5 = 3*5 + 2? Korrekt.


32

Division als Pseudo-Code

function divide(x,y) Input: Zwei ganze n-Bit Zahlen x,y mit y >= 1

Output: Quotient q und Rest r von x / y if x=0: return (q,r) = (0,0) (q,r) = divide(xx/2y,y) q = 2*q, r = 2*r if x is odd (ungerade): r = r + 1 if r >= y: r = r-y, q = q+1 return (q,r)

Aufwand ist übrigens wieder O(n2)


33

Modulare Arithmetik

Wenn man wiederholt addiert oder multipliziert, können große Zahlen entstehen - manchmal umgeht man das, in dem man die Zahl auf 0 zurücksetzt: Beim Zählen der Stunden setzen wir 24 und 0 gleich und beginnen

erneut usw. Wir definieren:

x modulo N sei der Rest, der bleibt, wenn x durch N geteilt wird, d.h. falls x = q*N+r mit 0<=r<N, dann gilt:

x modulo N = r Mit Bezug zu modulo N kann man jetzt sagen: zwei Zahlen x,y sind

äquivalent, wenn sie den gleichen Rest beim Teilen durch N erzeugen, also wenn

x modulo N = y modulo N, oder, gleichwertig:N teilt (x-y) glatt, also ohne Rest

Genau dann schreiben wir auch: x ´ y (mod N)


34

Modulare Arithmetik

Beispiel: 253 ´ 13 (mod 60), denn

253 = 4*60 + 13, also Rest 13 13 = 0*60 + 13, wieder Rest 13 also 253 mod 60 = 13 mod 60 Oder anders: 253 – 13 = 240, 240 = 4*6 + 0, also läßt sich (253-13)

glatt durch 60 teilen. Das gilt natürlich auch für (13-253) = -240


35

Modulare Arithmetik

Modulare Arithmetik (z.B. modulo N) limitiert den Wertebereich für die Ergebnisse der arithmetischen Operation, im Beispiel auf [0,..,N-1]. Sobald man an die Grenzen stößt, beginnt man wieder auf der anderen Seite.

Man kann aber auch sagen, dass modulare Arithmetik mit allen ganzen Zahlen umgeht, diese allerdings in N sogenannte Äquivalenzklassen unterteilt.

Für jede Klasse gilt: {i + kN: k 2 Z} mit 0 <= i < N. Wenn N=3 gilt (also wir „modulo 3“ rechnen), dann gibt es 3 Äquivalenzklassen

… -9 -6 -3 0 3 6 9 … (Rest 0) … -8 -5 -2 1 4 7 10 … (Rest 1) … -7 -4 -1 2 5 8 11 … (Rest 2)

Für jedes Zahlenpaar x,x‘ in einer der Klassen gilt: x ´ x‘ (mod N)

Aus Sicht der „modulo N“-Operation sind die Zahlen x und x‘ nicht unterscheidbar.


36

Modulare Arithmetik

Man kann immer noch rechnen (Ersetzungsregel) Falls x ´ x‘ (mod N) und y ´ y‘ (mod N), dann

x + y ´ x‘ + y‘ (mod N) x * y ´ x‘ * y‘ (mod N)

Praktische Anwendung: sie wollen alle Folgen einer Staffel ihrer Lieblingsserie direkt hintereinander schauen (z.B. House), und sie wollen um Mitternacht damit beginnen. Um wieviel Uhr sind sie fertig? (den Tag ignorieren wir mal ;) Es gibt 25 Episoden, jede dauert 3 Stunden (oops), also sind sie um (25

* 3) mod 24 Uhr fertig. Nun ist 25 ´ 1 (mod 24), also gilt mit der Regel oben 1 * 3 = 3 mod 24,

also um 3 Uhr am morgen. mit 25 *3 = 75 = 3*24 + 3 wären sie natürlich zum gleichen Ergebnis

gekommen – sie mußten aber nie die vergleichsweise großen Zahlen 75 und 72 bestimmen.


37

Modulare Arithmetik

Die üblichen Gesetze gelten auch „modulo“: x + (y + z) ´ (x + y) + z (mod N) x * y ´ y * x (mod N) x (y + z) ´ x * y + x * z (mod N)

Die erste ist die Assoziativitätsregel, die zweite die Kommutativitätsregel, die dritte die Distributivitätsregel.

Gemeinsam mit der Ersetzungsregel von der letzten Folie ermöglicht das, dass jedes Zwischenresultat bei „modulo“-Rechungen durch die Restbildung (also eine „modulo“-Operation) vereinfacht werden kann.

Das werden wir noch nutzen (auch in der Klausur!) Rechnen sie bitte: (278 * 35 * 17 * 78) modulo 13


38

Asymmetrische Verschlüsselung

Wir brauchen SCHLÜSSELPAARE, z.B. s und s‘ s‘ kann entschlüsseln, was s verschlüsselt … … und umgekehrt. Wie geht so etwas? Nehmen wir einen sehr einfachen Schlüssel, um das Alphabet A,..,Z zu

verschlüsseln: Jedem Buchstaben ist eine Zahl zwischen 0 und 25 zugeordnet, wir

nehmen eine sehr einfache Zuordnung: A/0, B/1, C/2, D/3, E/4, …, Z/25

Unsere Schlüssel s und s‘ rechnen auf dieser Repräsentation als Zahl: s(x) = (x + 3) modulo 26 s‘(x) = (x – 3) modulo 26

Test: F ! 5: s(5) = 8, s‘(8) = 5 Z ! 25: s(25) = 2, s‘(2) = 25


39


Die Schlüssel: s(x) = (x + 3) modulo 26 s‘(x) = (x – 3) modulo 26

s(GELSENKIRCHEN) = JHOVHQNLUFKHQ s‘(JHOVHQNLUFKHQ) = GELSENKIRCHEN

s‘(GELSENKIRCHEN) = DBIPBKHFOZEBK s(DBIPBKHFOZEBK) = GELSENKIRCHEN

Verschlüsseln sie: INFORMATIK mit s und s‘

X Y Z|A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z|A B C


40


Die Idee ist klar: Was der eine Schlüssel tut, nimmt der andere zurück… Er „invertiert“ jeweils, was der andere Schlüssel tat Wir suchen also ein Paar aus Operation und hierzu inverser Operation … und natürlich können die nicht so einfach sein, wie unser Schlüsselpaar

gerade Es wird noch ein wenig anderes funktionieren:

Wir legen Operationen fest und suchen nach Zahlen (nach 3, um genau zu sein), die dann in den Operationen verwendet werden und deren Effekte sich jeweils invers zu einander verhalten

Genau das haben wir eben auch gemacht: Die Operation war Addition. s addierte 3 und s‘ das Inverse von 3 bzgl. der

Addition, also -3. Genauso gut hätten wir multiplizieren können (z.B. mit 5 und 1/5,

allerdings dann ohne etwa abzuschneiden ;) Wir werden zwei Zahlen nutzen, die beim Potenzieren unter modulo

bezüglich einer dritten Zahl die Eigenschaft haben, invers zueinander zu sein.

Date post:	05-Apr-2015
Category:	Documents
Upload:	ricarda-borgwardt
View:	107 times
Download:	0 times

Prof. Dr. W. Conen, FH Gelsenkirchen, Version 1.21 LDS – Exkurs: Rechnen… Prof. Dr. Wolfram...

Documents