Ich versuche grade den kleinen fermatschen satz zu verstehen…
hab mir diese seite angeschaut und verstehe eine gewisses Zeichen nicht.
„http://www.mathepedia.de/Satz_von_Fermat.aspx“
Wir müssen zeigen, dass p | (a^p - p) ist.
Mittels vollständiger Induktion über a ergibt sich:
Induktionsanfang: 0^p - 0 = 0 ist durch p teilbar.
- Was bedeutet dieser senkrechter Strich nach p?
- Könnte mir jemand erzählen wie ich durch die vollständige Induktion auf 0^p - 0 komme…
Ich lerne grad das RSA-Verfahren und habe das halbwegs verstanden… aber ich glaub mir fehlen doch ein paar mathematische Kentnisse 
Hey Haruna,
p | (a^p - p)
bedeutet nichts anderes als, p teilt (a^p-p).
Bei der Induktion soll man ja im Induktionsanfang das kleinste Element für a (in deinem Fall) testen, das man einsetzen kann.
Also wird einfach die Formel erstmal für a=0 gestestet - und siehe da, die Null ist durch jede Zahl teilbar, also stimmt diese Formel für a=0.
Gruß René
Was bedeutet denn p teilt (a^p-p) ? weil (a^p-p) ist ja nicht durch p teilbar…
und wenn man a=0 setzt, wieso ist denn dann 0^p - 0 und nicht 0^p - p ??
Hey Haruna,
weil (a^p-p) ist ja nicht durch p teilbar
Das ist richtig - da scheint ein Fehler zu sein, da die eigentliche Formel a^p - a heißen müsste. Schließlich war die Grundlage ja
a\equiv a^p\mod p
Gruß René
vielleicht sollte ich mir doch ein buch suchen und nicht aus dem Internet lernen…
Könntest du mir vielleicht auch hierbei helfen??
(9*b) mod 26 = 1
Ich weiß nicht wie ich das auflöse… und ich versteh auch nicht wie inverse modulo geht… was ich glaube brauche…
Danke für deine Hilfe soweit.
Hey Haruna,
(9*b) mod 26 = 1
In welchem Zusammenhang kam diese Gleichung?
Oder sollte man nur bestimmen, für welche Werte von b diese Gleichung erfüllt ist?
In diesem Fall kann man es relativ einfach rausfinden:
Eine Zahl, welche modulo 26 gleich 1 ist, ist z.B. die 27. So ist b=3 schon mal eine Lösung. Außerdem ist somit jede weitere Lösung für die Gleichung 3 plus ein Vielfaches von 26 - daraus folgt, dass b = 3 + k * 26 für jede ganze Zahl k.
Gruß René
Also warum ich das alles lerne ist, weil ich bald kryptographie klausur schreibe.
Eine Aufgabe war halt…
Berechnen Sie die Dechiffrier-Funktion m=((c-k)*b)mod n, wobei das Modulo-Inverse b zu t=9 mittels des erweiterten Algorithmus zu bestimmes ist (raten gilt nicht).
Vorher mussten man ein Wort verschlüsseln mit c=((m*t)+k) mod n mit t=9 k=4 und n=26… A hat den Wert 0, B=1, C=2, … Z=25
also da ich ja ein Wort schon verschlüsselt habe weiß ich ja dass wenn m=10 ist, der verschlüsselte Buchstabe dazu c=16 ist…
und dann kommt in der gleichung: m=((c-k)*b)mod n
–> b=3+k*26
aber wie mache ich das wenn ich m nicht kenne… und was meint man in der aufgabe modulo-inverse b zu t=9 ermitteln.
Wäre echt sehr nett wenn du mir dabei auch noch helfen kannst? 
oke ich glaub ich bin weiter gekommen…
also c=((m*t)+k mod n … nach m auflösen.
[=] sei das Kongruentzeichen
c[=]m*t+k mod 26
c-k[=]m*t mod 26
und dann müsst wahrscheinlich dieses modulo inverse t’ berechnen…
(c-k*t’)[=] m mod 26
aber was ist denn t’ ??
fast verstanden =D
Ich habs endlich verstanden…
man nimmt das t=9 und das n=26…
der ggT(9,26)= 1
nun sucht man nach dem erweiterten euklidischen Algorithmus das t’…
indem man 1=x*t+y*n setzt… 1=x*9+y*26
und wie in wikipedia die tabelle zb ausfüllt…
http://de.wikipedia.org/wiki/Erweiterter_euklidische…
und am ende bekommt man 1=3*9+(-1)*26 raus… das x ist das inverse modulo von t…
t’=3 c=16 k=4 n=26
(c-k)*t’[=] m mod n
(16-4)*3 mod 26 = 10
m=10 !!!
Was ich noch nicht ganz verstehe ist…
(c-k)*t’[=] m mod n
36 [=] m mod 26
36 mod 26 = m mod 26