4. Modulare Arithmetik

Modulare Arithmetik

  • S

    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 😕

    0
  • V

    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*13    16 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(pk)=pk-p^(k-1) führen. Ah, so stehts in Wikipedia.

    Meine ist gleich, wegen pk-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;
}
    0
  • O

    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 🙂

    0
  • ?

    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)2)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+x    17)^(1) ≡ 3 (mod 4)
    13+x*17 ≡ 3 (mod 4)

    0
  • ?

    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?

    0
  • S

    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...

    0
  • V

    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.

    0
  • S

    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...

    0
  • ?

    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)

    0
  • ?

    Sqwan schrieb:

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

    Ohhhh!

    0
  • Mod

    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?

    0
  • S

    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 21010^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.

    ∑k=1201(1k+2)−∑k=4204(1k−2)\sum_{k=1}^{201}(\frac{1}{k+2}) - \sum_{k=4}^{204}(\frac{1}{k-2})

    summe dann rein gezogen...

    202∑k=1201(k)+404−202∑k=4204(k)−404\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...

    0
  • J

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

    0
  • J

    Sqwan schrieb:

    ∑k=1201(1k+2)−∑k=4204(1k−2)\sum_{k=1}^{201}(\frac{1}{k+2}) - \sum_{k=4}^{204}(\frac{1}{k-2})

    summe dann rein gezogen...

    202∑k=1201(k)+404−202∑k=4204(k)−404\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.

    0
Anmelden zum Antworten