Modulare Arithmetik

Sqwan

drei ist die lösung für 13 + x * 17

Es war zufall das meine Beispielaufgabe der a) auf der Probeklausur so ähnlich ist. Die hatte ich vorher noch nicht gesehen gehabt.

@KasF
Ich bin dir echt dankbar für jegliche Hilfe. Aber ich habe das Gefühl, das ist ein riesen Durcheinander in deinem Beitrag. Leider kann ich da keinen roten Faden erkennen.

otze

Naja, was KasF sagte ist nichts weiter als: du musst die Eigenschaften des Körpers kennen, in dem du rechnest. in diesem Fall war das der Satz von Euler.

In modulokörpern sind viele Dinge nicht mehr so einfach, wie im normalen Raum. bereits dass du dort sowas wie

y^31=3 (mod 4)

stehen hast ist kritisch. stände da nicht (mod 4) sondern (mod 546432) dann könntest du an der Aufgabe sehr sehr sehr lange rechnen, weil das diskrete Logarithmusproblem NP-Hart ist. Es gibt halt nicht mehr Tipps als: lerne die Theoreme des Körpers(die wichtigsten hat KasF aufgezählt) und dann setze sie intelligent ein.

Sqwan

Nun, recht hast du sicherlich. Leider schaffe ich das nicht mehr rechtzeitig.
Deshalb wäre es schön wenn KasF noch mal etwas ausführlicher beschreiben könnte wie er die Potenz zerlegt hat.

Das habe ich noch nicht ganz verstanden.
Also wie aus

^31 = 3 (mod 4) 
^2  = 1 (mod 4)

wurde.
Das andere sollte ich verstanden haben. Kanns dann jedenfalls mal selber mit was anderem testen...

Muss das dann nachlernen wird im Studium sicher wiederkommen. Ist bei uns im Script leider als Vorwissen markiert, weshalb es nicht in der Vorlesung vor kam...

volkard

Sqwan schrieb:

Also wie aus
^31 = 3 (mod 4) 
^2  = 1 (mod 4)
wurde.

Normale Potenzenrechnung.
x^31
=x*x*x*x...*x(31 Stück)
=x*x*x*...*x(15 Stück) * x*x*x*...*x(15 Stück) * x
=x^15 * x^15 * x^1
=(x¹⁵⁾2 * x^1
UUps, er hat es ja andersrum zerlegt
=x*x * x*x * x*x * ... * x*x(15 Päärchen) * x
=(x*x)^15 * x
=(x²⁾15 *x^1
Ups, Frage nicht verstanden und nur einen kleinen Aspekt beleuchtet.

otze

Das ist eine wichtige Eigenschaft endlicher Körper, die leider nicht so einfach zu beweisen ist. Insbesondere weil dein modulo nicht prim ist, muss man da sehr viel Theorie durchschleifen.

Aber nur mal als Skizze: Man kann beweisen, dass wenn man für ein beliebiges Element a mit ggt(a,n)=1 (n ist der Modulowert) die Reihe a^1 a^2 a^3... berechnet man eine Zahlenreihe bekommt, bei der am Ende immer die 1 steht und die dann zyklisch weiter geht. Dies geht relativ einfach durch einen Widerspruchsbeweis den ich einfach mal skizziere:
für jedes Element a mit ggt(a,n)=1 gibt es ein Inverses a^-1(Eigenschaft der multiplikativen Gruppe).
Angenommen, die Aussage ist falsch, dann gibt es kein i für das gilt: 1=a^i=a(i-1)*a=a^-1*a eine Potenz von a ist dann niemals die Inverse von a.
Nun kommt ein Schubladenargument: in einem finiten Körper kann es nur endlich viele Rechenergebnisse geben. Wenn wir also ausschließen, dass die Inverse das Ergebnis sein kann, dann muss(!) ein Ergebnis doppelt rauskommen. Das kann aber nicht sein, weil wir eine Gruppe haben und damit x*a!=y*a für x!=y gelten muss! => Widerspruch zur Annahme.
Das i für das a^i=1 gilt, nennt man die "Elementordnung" von a.

Dann kann man lustig weiterbeweisen und zeigen, dass die Elementordnung immer die Anzahl der Elemente einer Gruppe teilt. Die Gruppenordnung erhälst du durch die Eulersche Phi-Funktion und damit schließt sich der Kreis: a^phi(n)=a(i*x)=(aⁱ⁾x=1^x=1
In deinem Fall ist phi(n)=2 (kannst du dir überlegen: 1 ist drin, 2 ist nicht drin wegen 2*2=0 und 3 ist wieder drin wegen 3*3=9 mod 4=1). Und nun schauste dir das von KasF nochmal an.

Sqwan

Danke volkard, aber das grade nicht gemeint.
Das hattest du mir damals mal so gut erklärt das hab ich behalten

Mir gehts eigentlich darum wie man phi berechnet...
otze hat da schon mal sehr geholfen.
Leider passt es noch nicht ganz.

Wenn ich mod 4 habe kann ich mir das noch recht einfach ausdenken. So wie ich das jetzt verstanden habe. Die frage ist nur, kann ich das auch berechnen.

Sicher bin ich mir nicht...
http://de.wikipedia.org/wiki/Eulersche_φ-Funktion
Da habe ich mich mal umgesehen.
Also da scheint nicht zu stehen wie es geht. Allerdings gibt es dort eine liste von 1 bis 99.
Da kann ich jetzt mit zerlegung arbeiten. War was ist bei potenzen die sehr hoch sind? 5681 zum beispiel?

Dann stellt sich mir die frage, wie genau wird dieser ggt berechnet...
Weil X ist ja unbekannt

vllt kann mir noch mal einer sagen wie genau für die funktion (13 + x * 17)^31 der ggt berechnet wird. und anschließend wie ich aus a^φ(4) oder auch 6 oder 10 mein phi berechne...

Das will mir einfach noch nicht so ganz klar werden...

EDIT: was mir noch aufgefallen ist:
bei ^32 hätte ich ein problem da 2*16+0 raus käme

volkard

Sqwan schrieb:

Da kann ich jetzt mit zerlegung arbeiten. War was ist bei potenzen die sehr hoch sind? 5681 zum beispiel?

Irgendwie ganz einfach irgendwie, nur ist Wikipedia-Mathematik wie immer nicht lesen.
Zum Testsn, ob deine Vermutung stimmt, bietet sich schonmal
http://www.wolframalpha.com/input/?i=phi(5681)
an.
Und bestimmt auch
http://www.wolframalpha.com/input/?i=factor(5681)
Ach ,ja, dann ist es einfach 12*18*22

Bei Primzahlenpotentzen drin wie bei 13*13*1317=37349 gehts ein wenig anders.
Irgendwie kommt 12*13*1316 raus. Als wenn ein Primfaktor nur einmal das Recht hätte, als p-1 aufzutauchen und bei allen folgenden das nicht mehr darf.

Ob das Sinn ergibt? Mal phi(27) anschauen.
27=3*3*3.
Es fallen nur 9 Zahlen raus, nämlich die durch 3 teilbaren. Durch 9 teilbare oder durch 27 teilbare sind ja schon raus, weil die ebenfalls durch 3 teilbar sind.
Das würde zur Formel phi(p^k)=pk-p^(k-1) führen. Ah, so stehts in Wikipedia.

Meine ist gleich, wegen p^k-p(k-1) = p*p^(k-1)-1*p(k-1) = (p-1)*p^(k-1)

Edit: Bisher dachte ich immer, man müsse zuerst die Primfaktoren sammeln und danach die Formel anwenden.
Anscheinen nicht. Mal den Trick eingetippt.

unsigned int phi(unsigned int n){
	unsigned int result=1;
	for(unsigned int t=2;n!=1;++t){
		if(n%t==0){
			result*=(t-1);
			n/=t;
			while(n%t==0){
				result*=t;
				n/=t;
			}
		}
	}
	return result;
}

otze

Sqwan schrieb:

EDIT: was mir noch aufgefallen ist:
bei ^32 hätte ich ein problem da 2*16+0 raus käme

Ja, für ^32 hat die Gleichung auch keine Lösung.

es muss ja auch nicht immer eine Lösung geben

Hmmm,
war das echt so durcheinander ... naja, wie auch immer.

Nochmal zum Trick mit dem Runterbrechen der Potenz.

Du hasst ja folgende Gleichung:
(13+x*17)^31 ≡ 3 (mod 4) [1]

und dank Euler weißt du folgendes:
(13+x*17)^2 ≡ 1 (mod 4) [2]

Nun müssen wir den Euler irgendwie in unsere Gleichung einbringen. Um [2] in [1] einsetzen zu können, müssen wir [1] in eine Form bringen, in die wir [2] einsetzen können. Dh wir brauchen irgendwie in [1] > (13+x*17)^2 < drin. Also irgendwie ein ^2

Dafür wenden wir die Potenzgesetze an [1] an:
(13+x*17)^31 ≡ 3 (mod 4)

(13+x*17)^(2*15+1) ≡ 3 (mod 4) -- Dort steht ne 2, das ist für uns gut

(13+x*17)^(2*15) * (13+x*17)^(1) ≡ 3 (mod 4) -- Addition der Exponenten, ist Multiplikation der Potenzen

((13+x*17)²⁾15 * (13+x*17)^(1) ≡ 3 (mod 4) -- Mutli Multi macht Expo Expo

Nun da steht jetzt unsere tolle (13+x*17)^2 und dank Euler wissen wir das dies modulo 4 gleich 1 ist. Also 1 einsetzen:

(1)^15 * (13+x17)^(1) ≡ 3 (mod 4)
(13+x17)^(1) ≡ 3 (mod 4)
13+x*17 ≡ 3 (mod 4)

ey, was solln das hier, wo ist das problem, sich für x einfach mal eine tabelle zu erstellen, also zu Fuß ausrechnen, und dann gucken, was rumkommt?

Sqwan

und dank Euler weißt du folgendes:
(13+x*17)^2 ≡ 1 (mod 4) [2]

Eben das weiß ich nicht... Den rest habe ich verstanden. Da liegt das problem. das zu berechnen...

Bullshit schrieb:

ey, was solln das hier, wo ist das problem, sich für x einfach mal eine tabelle zu erstellen, also zu Fuß ausrechnen, und dann gucken, was rumkommt?

So du Held, dann mach mir doch mal ne tabelle für alle X
(13+x*17)^133789513 ≡ 531 (mod 199417)
Ich bin gespannt auf die Tabelle... Und erst auf den Fußweg ^^
Du solltest wissen das eine eine Klausur über 1 std geht, du 5 Aufgaben zu lösen hast, von der sowas ein Teil von Aufgabe 1 ist, die aus ca 5 Teilen besteht...

volkard

199417 = ...
Per Taschenrechner keine Teiler unter 33 gefunden.
In der Tat ist das eine Primzahl. Und das zu zeigen kann nicht Teil der Klausur sein.
Dein Mimimi ist zu unvollständig.

(13+x*17)^133789513 ≡ 531 (mod 199417)
z^133789513 = 531 (mod 199417)
phi(199417)=199416
133789513%199416=180793
Und dann würde fastexp ansetzten. 199416 hat glaub ich nur 18 Bit. Ewig kanns nicht dauern.

Sqwan

nein... in der tat ist es das nicht. es war auch nur ein beispiel um zu zeigen das "einfach alle x testen" nicht der weg sein kann.

Ich häng immernoch an der scheiß bestimmung von phi... Offentlich krieg ich das bis montag morgen noch raus...

Die eulerische Funktion ist dein Problem ?

Also, die Funktion gibt dir zur Zahl x an, wieviele teilerfremde es zu x zwischen 1 und x gibt. Teilerfremd heißt einfach gesagt, wenn die zwei Zahlen in einem Bruch als Nenner und Zähler vorkommen, nicht mehr kürzbar sind.

zB: 1/3 --> hier kann man nicht weiter kürzen, dh sie sind teilerfremd, da sie keinen gemeinsamen "kürzer" (teiler) mehr haben.

genauso wie: 3/8, 12/17, 5/2 etc ... Diese Zahlen haben einen ggT = 1.

Wenn du jetzt phi(6) berechnen willst, schaust du dir die Zahlen von 1-5 an:

size_t count = 0;
1/6 -> Teilerfremd ++count;
2/6 -> BIEP (Teiler 2 möglich)
3/6 -> BIEP (Teiler 3 möglich)
4/6 -> BIEP (Teiler 2 möglich)
5/6 -> Teilerfremd ++count;

count = 2!

Das heißt phi(6) ist gleich 2. Und jetzt noch was interessantes. phi(primzahl) ist immer primzahl-1. Denn ne Primzahl hat -wie üblich- keinen Teiler, daher sind alle Zahlen kleiner x (=prim) Teilerfemd zu x.

Beispiel phi(5):
1/6 -> Teilerfremd ++count;
2/6 -> Teilerfremd ++count;
3/6 -> Teilerfremd ++count;
4/6 -> Teilerfremd ++count;

phi(5) = 4, genauso wie phi(3) = 2, phi(17) = 16 usw.
Und jetzt noch was schönes. Laut einem tollen Satz der Mathematik lassen sich alle Zahlen in Primfaktoren zerlegen. zB 9 = 3*3 oder 15 = 5*3.
Das kannst du auch bei der Berechnung von phi() benutzen, denn es gilt:

phi(a*b) = phi(a) * phi(b)

Achtung, gilt aber nur für a,b = prim und a!=b (s.u.). Also phi(80) != phi(10) * phi(8), eher phi(80) = phi(2*2*2*2*5). Und hier kommt direkt noch die nächste Regel ins Spiel.

phi(2*2*2*2*5) = phi(2^4) * phi(5) .. Sobald ne Primpotenz in phi auftauch, also zb phi(2*2) = phi(2^2) gilt

phi(p^k) = p^k - p^(k-1)

Also zurück zur 80:
phi(80) = phi(2^4 * 5) = phi(2^4) * phi(5) = [2^4 - 2^(4-1)] * 4 = 32

All dies wird auch ganz schön bei RSA ausgenutzt. Nochmal alls summengefasst:

phi(x) = Anzahl aller Teilerfremden zu x, zwischen 1 und x

phi(prim) = prim-1
phi(primA*primB) = (primA-1)*(primB-1)
phi(prim^k) = prim^k - prim^(k-1)

Sqwan schrieb:

Offentlich krieg ich das bis montag morgen noch raus...

Ohhhh!

SeppJ

KasF schrieb:

Sqwan schrieb:

Offentlich krieg ich das bis montag morgen noch raus...

Ohhhh!

Die Klausur müsste ja nun zu Ende sein.
@Sqwan: Wie war's? Gut modulo gerechnet und schön Summen vereinfacht?

Sqwan

naja... war so ne sache ^^
(2^501 + 37) mod 4 galt es zu berechnen.

Da ioch phi nicht berechnen konnte habe ich acuh das raus erstmal (2^501 mod 4 + 37 mod 4) gemacht.
Daraus dann 2¹⁰10^5 mod 4 * 2^1 mod4 + 37 mod 4 wo dann ein rest von 3 bei raus kam.
Obs richtig ist weiß ich noch nicht.

Summen habe ich auch schön "versucht" zu vereinfachen, ist aber wohl falsch denke ich.

$\sum_{k=1}^{201}(\frac{1}{k+2}) - \sum_{k=4}^{204}(\frac{1}{k-2})$

summe dann rein gezogen...

$\frac{202}{\sum_{k=1}^{201}(k)+404} - \frac{202}{\sum_{k=4}^{204}(k)-404}$

ergebnis sollte -401 sein, war aber es bei mir aber nicht...
Also ein Fehler beim verwenden der summe...

Jester

(2^501+37) mod 4 = 2^501 mod 4 + 37 mod 4 = 4*2^499 mod 4 + 1 = 1

Jester

Sqwan schrieb:

$\sum_{k=1}^{201}(\frac{1}{k+2}) - \sum_{k=4}^{204}(\frac{1}{k-2})$

summe dann rein gezogen...

$\frac{202}{\sum_{k=1}^{201}(k)+404} - \frac{202}{\sum_{k=4}^{204}(k)-404}$

aua, denkst Du auch dass 1/2 + 1/2 zusammen 1/4 ergibt?

edit: Ah, Du hast oben auch erweitert... dann hast du einfach nur erweitert und das Summenzeichen unterwegs verloren...

In der zweiten Summe einfach k durch k+4 ersetzen. Dann lässt die sich umschreiben als $$\sum_{k=0}^{200} \frac{1}{k+2}$. Danach kann man prima sehen, dass genau 1/203 - 1/2 übrig bleibt. Alle weiteren Terme sind in beiden Summanden enthalten und heben sich daher auf.