Rechnen modulo n - TU Dresden

1 Rechnen modulonBernhard GanterInstitut f ur AlgebraTU DresdenD-01062 Ganter, TU DresdenMathematik I f ur InformatikerKanonische PrimfaktorzerlegungJede nat urliche Zahln>0 kann auf eindeutige Weise in der Formn=p 11 p 22 .. p kkgeschrieben werden, wobeik N, i N\{0}f uri {1,..,k}undp1<p2< <pkPrimzahlen ist diekanonische Ganter, TU DresdenMathematik I f ur InformatikerggT und kgVJe zwei nat urliche Zahlennundmbesitzeneinen gr o ten gemeinsamen Teiler ggT(m,n) undein kleinstes gemeinsames Vielfaches kgV(m,n).Zur Bestimmung des ggT kann man den Algorithmus derWechselwegnahmebenutzen:whilem6=ndobe ginifm<nthenn:=n mifn<mthenm:=m nendoutput( ggT = , m).Bernhard Ganter, TU DresdenMathematik I f ur InformatikerGauss KlammerIstreine reelle Zahl, dann bezeichnetbrcdie gr o te ganze Zahl,die kleiner oder istdredie kleinste ganze Zahl, die gr o er oder Zahlen,b6= 0, so istadivb= ab.

2 Bernhard Ganter, TU DresdenMathematik I f ur InformatikerzmodnIstzeine beliebige ganze Zahl und istn>0 eine nat urliche Zahl,dann istzmodn:=z n zn .Beispielsweise ist17 mod 5 = 2 und 17 mod 5 = jedem Falle giltzmodn {0,1,..,n 1}.Bernhard Ganter, TU DresdenMathematik I f ur InformatikerRechnen modulonWenn man umfangreiche Rechnungen modulonauszuf uhren hat,dann ist dieHomomorphieregelau erordentlich hilfreich. Siebesagt, dass man auch Zwischenergebnisse modulonrechnen darf,ohne dass sich das Endergebnis andert. Formal besagt sie, dass f urganze Zahlena,bstets folgendes gilt:(a+b) modn= (amodn+bmodn) modn(a b) modn= (amodn bmodn) modn(a b) modn= (amodn bmodn) modnBernhard Ganter, TU DresdenMathematik I f ur Informatikera r(modn)Der st andige Zusatz modn wird rasch l astig und gernweggelassen. Um Missverst andnisse zu vermeiden, kann man ihnam Ende der Rechnung in Klammern angeben und dieGleichheitszeichen durch ersetzen, wie im folgenden Beispiel:(108 33) 22 (3 3) + 3 9 + 3 2(mod 5).

3 Stattamodn=rschreibt man oft aucha r(modn)und liest dies etwas altert umlich aber einpr agsam alsa ist kongruent zu r modulo Ganter, TU DresdenMathematik I f ur InformatikerEin Satz von Primzahlpist genau dann nicht als Summe zweierQuadrate ganzer Zahlen darstellbar, wennpkongruent zu3 modulo 4 Ergebnisse der elementaren Zahlentheorie haben in denletzten Jahren f ur dieKryptologiean Bedeutung Ganter, TU DresdenMathematik I f ur InformatikerRechnen modulo 5+0 1 2 3 400 1 2 3 411 2 3 4 022 3 4 0 133 4 0 1 244 0 1 2 3 0 1 2 3 400 4 3 2 111 0 4 3 222 1 0 4 333 2 1 0 444 3 2 1 0 0 1 2 3 400 0 0 0 010 1 2 3 420 2 4 1 330 3 1 4 240 4 3 2 1 Die Verkn upfungstafeln f ur die Rechenarten modulo Ganter, TU DresdenMathematik I f ur InformatikerOperationen auf einer MengeGrunds atzlich hat man nahezu unbegrenzte Freiheiten, sich neueRechenstrukturen zu verschaffen: Man w ahlt sich eineTr agermenge und definiert daraufOperationen, beispielsweiseindem man willk urlich Verkn upfungstafeln upfungbedeuten in diesem Zusammenhangdasselbe.

4 Einen-stellige Operation auf einer Tr agermengeTnimmt als Input eine Folge vonnElementen ausTund gibt einElement vonTals Output zur Operation aufTist also eine Abbildungf:Tn Ganter, TU DresdenMathematik I f ur InformatikerTischtennisturniermultiplika tionabcdeabcdePPPP aaaabcde abcdeSSSSSS abcde !!!x y:={xfallsx=y,der Spieler, der aussetzt, wennxgegenyspieltfallsx6= Ganter, TU DresdenMathematik I f ur InformatikerTischtennisturniermultiplika tionstafelabcdeabcdePPPP aaaabcde abcdeSSSSSS abcde !!! abcdeaadbecbdbecacbecaddecadbecadbeBernh ard Ganter, TU DresdenMathematik I f ur InformatikerRegeln (1) f ur das Rechnen modulonDie Additionist assoziativ: es gilt (a+b) +c=a+ (b+c)f ur allea,b,c,ist kommutativ: es gilta+b=b+af ur allea,b,istk urzbar: ausa+b=a+cfolgt stetsb= ist wichtig, wenn man Gleichungen l 0 alsneutrales Element:a+ 0 = 0 +a=agilt f ur Elemente: Zu jedemaist a:= 0 aein Element mita+ ( a) = 0 = ( a) +a.}

5 Daraus folgt ubrigensdie K urzbarkeit.(Zn,+modn, modn,0) ist eine abelsche Ganter, TU DresdenMathematik I f ur InformatikerRegeln (2) f ur das Rechnen modulondie Multiplikationist assoziativ: es gilt (a b) c=a (b c) f urallea,b,c,ist kommutativ: es gilta b=b af ur allea,b,hat 1 als neutrales Element:a 1 =a= 1 agiltf ur uber der Addition distributiv:a (b+c) =a b+a cgilt f ur allea,b,c(Leseregel: Punktrechnung vorStrichrechnung ).Zn:= (Zn,+modn, modn, modn,0,1)ist ein kommutativer Ring mit Ganter, TU DresdenMathematik I f ur InformatikerEin anderer Zugang zuZnF ur ZahlenmengenA,B Rdefiniert man dieKomplexadditiondurchA+B:={a+b|a A,b B}.Entsprechend kann man eineKomplexsubtraktionund eineKomplexmultiplikationeinf kommt man (wenn man noch Klammern einspart) f urnat urliche ZahlennundrzunZ+r:={..,r 2n,r n,r,r+n,r+ 2n,..},derRestklassezum Restrmodulon.

6 Diese Menge enth alt genaudiejenigen ganzen Zahlen, die bei der ganzzahligen Division durchnden Ganter, TU DresdenMathematik I f ur InformatikerRestklassenringeMan uberzeugt sich, dass bei festemndieKomplexaddition,Komplexsubtrak tion undKomplexmultiplikationvon Restklassen als Ergebnisse immer Restklassen Restklassen modulonbilden einen kommutativen Ring mitEins, denRestklassenringder ganzen Zahlen Ganter, TU DresdenMathematik I f ur InformatikerRechnen mit Repr asentantenJede Restklasse modulonenth alt genau eine der Zahlen{0,1,..,n 1}.Deshalb rechnet man nicht wirklich mit den Restklassen, sondernmit ihrenRepr entspricht genau der oben eingef uhrten Rechenweise Restklassenring modulonist also isomorph zum RingZnderganzen Zahlen Ganter, TU DresdenMathematik I f ur InformatikerRechnen modulo 2 Der f ur die Informatik wichtigste Fall ist nat urlichZ2.

7 In diesemFall stimmen Addition und Subtraktion uberein. Die beidenRestklassen sind die Menge der geraden und die der ungeradenZahlen.+0 100 111 0 0 100 010 1 Das Rechnen modulo Ganter, TU DresdenMathematik I f ur InformatikerDividieren modulon?EineDivisionmodulonkann man nicht ohne erheblicheEinschr ankungen zeigt ein einfaches Beispiel: das Rechnen modulo es m oglich w are, eine Division durch 2 modulo 6 zu erfinden,dann sollte doch jedenfalls 2 geteilt durch 2 das Ergebnis 1 und 0geteilt durch 2 das Ergebnis Null erh alt man die widerspr uchliche Gleichung3 3 1 3 22 3 22 02 0(mod 6).So geht es also nicht!Bernhard Ganter, TU DresdenMathematik I f ur InformatikerNullteilerMan kann dieses Beispiel nennt eine Zahla6= 0 (in einem Ring) einenNullteiler, wennes eine Zahlb6= 0 mita b= 0 RingZ6ist diese Bedingung f ura= 2 undb= 3 erf ullt:2 ist also ein Nullteiler Argumentation der vorigen Seite zeigt:eine Division durch Nullteilerkann nicht sinnvoll definiert Ganter, TU DresdenMathematik I f ur InformatikerEinheitenEine Zahlain einem Ring ist eineEinheit, wenn es eine Zahlbmita b= 1 Einheiten kann man dividieren , dennbverh alt sich ja wieein Kehrwert sagt,bseimultiplikativ dividiert durcha, indem man Ganter, TU DresdenMathematik I f ur InformatikerMittelwert mod 5 Auf diese Weise k onnen wir einen Mittelwert modulo 5 definieren, n amlich die Operationa b:= 3(a+b) mod 5,denn wegen 2 3 mod 5 = 1 ist 3(a+b) modulo 5 dasselbe wiea+b2.

8 0 1 2 3 400 3 1 4 213 1 4 2 021 4 2 0 334 2 0 3 142 0 3 1 Ganter, TU DresdenMathematik I f ur InformatikerTischtennis mod 5 Auf diese Weise k onnen wir einen Mittelwert modulo 5 definieren, n amlich die Operationa b:= 3(a+b) mod 5,denn wegen 2 3 mod 5 = 1 ist 3(a+b) modulo 5 dasselbe wiea+b2. abcdeaadbecbdbecacbecaddecadbecadbe = 0 1 2 3 400 3 1 4 213 1 4 2 021 4 2 0 334 2 0 3 142 0 3 1 Ganter, TU DresdenMathematik I f ur InformatikerWelche Zahlen sind Einheiten modn?Durch Einheiten kann man dividieren, durch Nullteiler bleibt die Frage, wie man Einheiten und Nullteiler das einfach:HilfssatzEine Zahla {1,..,n 1}ist genau dann eine Einheitmodulon, wennazunteilerfremd Einheit, dann istaein Ganter, TU DresdenMathematik I f ur InformatikerEulersche -FunktionDie Eulersche -Funktion ist f urn Nfolgenderma en definiert: (n) :=|{e {0.}}

9 ,n 1}|ggT(e,n) = 1}|. (n) gibt also die Anzahl der zunteilerfremden nat urlichen Zahlenan, die kleiner alsnsind. (n) gibt also auch die Anzahl der Einheiten Ganter, TU DresdenMathematik I f ur InformatikerEine Formel f ur (n)SatzIstn=p 11 p 22 .. p kkdie kanonische Primfaktorzerlegung vonn, dann gilt (n) =n (1 1p1) (1 1p2) (1 1pk).Beispiel: 1008 = 24 32 7, deshalb (1008) = 1008 (1 12) (1 13) (1 17) = 1008 12 23 67= Ganter, TU DresdenMathematik I f ur InformatikerFunktion WegnahmeInput: Eine Menge{a,b}, bestehend aus nat urlichen : WN({a,b}) :={{b,a b}fallsa b{a,b a} wird also die gr o ere der beiden Zahlen ersetzt durch diepositive Differenz der beiden Zahlen. Das Ergebnis ist eine zwei-oder einelementige Ganter, TU DresdenMathematik I f ur InformatikerEigenschaften der Funktion Wegnahme1 Ist{a1,b1}= WN({a,b}),dann gibt es ganze Zahlen 1, 2, 3, 4mita1= 1 a+ 2 bundb1= 3 a+ 4 {a1,b1}= WN({a,b}) und istdein gemeinsamer Teilervona1undb1, dann istdauch ein Teiler vonaund Ganter, TU DresdenMathematik I f ur InformatikerWechselwegnahmeAlgorithmus : Nat urliche Zahlena, |{a,b}|= 2 do{a,b}:= WN({a,b}).

10 Bei jedemwhile-Schritt die gr o ere der beiden Zahlenverkleinert wird, terminiert dieser Algorithmus offenbar, , erkommt zu einem Ganter, TU DresdenMathematik I f ur InformatikerBeispiel zur WechselwegnahmeInput:154238238 154 = 84also:15484154 84 = 70also:847084 70 = 14also:701470 14 = 56also:561456 14 = 42also:421442 14 = 28also:281428 14 = 14 Ganter, TU DresdenMathematik I f ur InformatikerggT-BerechnungHilfssatzDer AlgorithmusWechselwegnahmeberechnet dengr o ten gemeisamen Teiler (ggT).BeweisSeiddas Ergebnis einer Ausf uhrung des Algorithmus beidem Input{a,b}. Wendet man die Beobachtungen 1) und 2)induktiv an, so erh alt man:1Es gibt ganze Zahlen , mitd= a+ b, zweite zeigt, dassdein gemeinsamer Teiler vonaundbist,und aus dem ersten folgt, dass jeder gemeinsame Teiler vonaundbauch ein Teiler vondist. Deshalb mussdder gr o tegemeinsame Teiler Ganter, TU DresdenMathematik I f ur InformatikerBeobachtungEine Erkenntnis aus dem Beweis wollen wir als Satz festhalten, weilsie oft sehr n utzlich ist:SatzZu je zwei ganzen Zahlena,bexistieren ganze Zahlen , mitggT(a,b) = a+ Zahlen , kann man durch R uckw artseinsetzen beimAlgorithmus Wechselwegnahme leicht Ganter, TU DresdenMathematik I f ur InformatikerBeschleunigung der ggT-BerechnungAm Beispiel erkennt man eine M oglichkeit, den Algorithmus zubeschleunigen: die letzten vier Schritte kann man zu einemeinzigen : Nat urliche Zahlenaundbmita : MW(a,b) := (b,amodb).