4. Modulare Arithmetik

Modulare Arithmetik

  • ?

    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