Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

RSA Modulare Arithmetik
Gehe zu Seite 1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> RSA Modulare Arithmetik
 
Autor Nachricht
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 24 Aug 2005 - 15:48:16    Titel: RSA Modulare Arithmetik

Ich schreib meine Facharbeit über den RSA-Algorithmus, der ja maßgeblich auf dem modulo-Operator aufbaut. Das Problem ist, dass ich den Unterschied zwischen

a = b mod n und
a # b mod n ( das # soll so ein "Gleichheitszeichen" mit 3 Strichen sein )

finden kann.

Das mit dem # heißt doch Kongruenz und bedeutet, dass a mod n = b mod n ist, oder??? SO hab ich dass verstanden. Hier für gibt es ausreichend Rechenregeln.

Ich bräuchte aber die einfachen Rechenregeln für a = b mod n!!! ( Also Addition, Multiplikation und Potenzierung )

Ist also z. B. ( b mod n )^2 = (b^2) mod n ? Ich würde sagen diese Gelichung ist falsch...

Das Problem ist, dass ich nur Rechenregeln für Kongruenzen finde und nicht für einfache mod-Operationen...

Wär toll wenn mir jemand helfen könnte oder interessante Links kennt! Danke schon mal...


Zuletzt bearbeitet von Charge69 am 24 Aug 2005 - 15:58:13, insgesamt einmal bearbeitet
Whoooo
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 08.06.2005
Beiträge: 8988

BeitragVerfasst am: 24 Aug 2005 - 15:50:34    Titel:

kann dir auf die schnelle nur die beiden aus der wikipedia liefern, sehn aber ganz brauchbar aus:
http://de.wikipedia.org/wiki/Modulo
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 24 Aug 2005 - 15:56:52    Titel:

Die kenn ich schon! Ist aber nicht direkt, dass was ich suche..
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 24 Aug 2005 - 16:19:08    Titel:

Kannst Du mal was angeben, wofür Du solche Regeln beötigst?
xaggi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 15.03.2004
Beiträge: 1190

BeitragVerfasst am: 24 Aug 2005 - 16:27:23    Titel:

Zitat:
a = b mod n


Sowas gibt es m.E. nicht. Jedenfalls hat es nix mit Mathematik zu tun.

Zwei ganze zahlen können kongruent modulo einer natürlichen Zahl sein.

mod als operation gibts afaik nur in der informatik, und ist dann eine funktion mit zwei parametern, die den rest der ganzzahldivision liefert.
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 24 Aug 2005 - 16:32:07    Titel:

a = b mod n gibt's schon, is allerdings ein Spezialfall.
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 24 Aug 2005 - 16:37:19    Titel:

xaggi hat folgendes geschrieben:
Zitat:
a = b mod n


Sowas gibt es m.E. nicht. Jedenfalls hat es nix mit Mathematik zu tun.

Zwei ganze zahlen können kongruent modulo einer natürlichen Zahl sein.

mod als operation gibts afaik nur in der informatik, und ist dann eine funktion mit zwei parametern, die den rest der ganzzahldivision liefert.


Warum gibt es das nicht?? Ich brauch es zwar für Informatik, aber das muss es doch auch in der Mathematik geben!

Man kann doch sagen 16 mod 7 = 2. Was ist denn daran falsch?
Es muss doch irgendwelche Rechenregeln dafür geben...

z.B. Addition:

a = b mod n
c = d mod n

a + c = b mod n + d mod n = ( b + d ) mod n

also z.B 16 mod 7 + 22 mod 7 = 2 + 1 = 3

( 16 + 22 ) mod 7 = 38 mod 7 = 3

scheint für Addition zu stimmen... Wie siehts denn mit Multiplikation und Potenzen aus?


Brauchen tu ich's hierfür:

Ich frage mich ob das stimmt:


Upps: Tut mir leid ignoriert die vierte Zeile einfach, die is aus Versehen doppelt...
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 24 Aug 2005 - 17:10:33    Titel:

Charge69 hat folgendes geschrieben:
xaggi hat folgendes geschrieben:
Zitat:
a = b mod n

Man kann doch sagen 16 mod 7 = 2. Was ist denn daran falsch?
Das ist solch ein Spezialfall.


Zitat:


Die letzte Zeile stimmt im allgemeinen nicht. Stattdessen gilt:
m^(1+k*Phi(n)) mod n = m mod n
Deine Zeile gilt nur für m<n.

Ähnlich ist es mit der Addition:
Zitat:
a = b mod n
c = d mod n

a + c = b mod n + d mod n = ( b + d ) mod n

also z.B 16 mod 7 + 22 mod 7 = 2 + 1 = 3

( 16 + 22 ) mod 7 = 38 mod 7 = 3

Auch ein günstiger Spezialfall. Für a=2, b=5, c=2, d=2 und n=3.
a=b mod n, c=d mod n, aber
b mod n + d mod n = 4 =|= 1 = (b+d) mod n
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 24 Aug 2005 - 17:23:18    Titel:

Hiob hat folgendes geschrieben:
Charge69 hat folgendes geschrieben:
xaggi hat folgendes geschrieben:
Zitat:
a = b mod n

Man kann doch sagen 16 mod 7 = 2. Was ist denn daran falsch?
Das ist solch ein Spezialfall.


Zitat:


Die letzte Zeile stimmt im allgemeinen nicht. Stattdessen gilt:
m^(1+k*Phi(n)) mod n = m mod n
Deine Zeile gilt nur für m<n.

Ähnlich ist es mit der Addition:
Zitat:
a = b mod n
c = d mod n

a + c = b mod n + d mod n = ( b + d ) mod n

also z.B 16 mod 7 + 22 mod 7 = 2 + 1 = 3

( 16 + 22 ) mod 7 = 38 mod 7 = 3

Auch ein günstiger Spezialfall. Für a=2, b=5, c=2, d=2 und n=3.
a=b mod n, c=d mod n, aber
b mod n + d mod n = 4 =|= 1 = (b+d) mod n


Danke für die schnelle Antwort. Für meinen Fall ist Voraussetzung m<n! Also gilt meine Rechnung dann... Very Happy

Das Problem ist aber, woher weiss ich denn, ob dass jetzt stimmt oder nicht, wenn ich allgemein rechne? Ist denn alles ein Spezialfall? Gibts keine (eingeschränkten)Rechenregeln für typische Beziehungen oder sowas?
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 25 Aug 2005 - 02:09:30    Titel:

a mod n + b mod n = ( a + b ) mod n

Das gilt, wenn gilt:
0 <= a mod n + b mod n < n.

Bsp:

Behauptung: a mod n + b mod n = ( a + b ) mod n
Annahme a=150, b=5, n=17:
Dann ergibt sich:
150 mod 17 + 5 mod 17 = 14 + 5 = 19 =|= 2 = 155 mod 17 = (150 + 5) mod 17
Also gilt auch:
150 mod 17 + 5 mod 17 =|= (150 + 5) mod 17
Das widerspricht der Behauotung und damit ist die Behauptung falsch. Sie gilt nur in speziellen Fällen.

Wenn man eine Kongruenz mod n von zwei Termen gegeben hat, dann schreibt man als Gleichung erst den Term links vom Kongruenzzeichen in Klammern, dann "mod n", dann "=", dann den Term rechts vom Kongruenzzeichen ohne "mod n" in Klammern und dahinter wieder "mod n".
a # b mod n
wird zu
(<Term vor #>) mod n = (<Term nach # ohne mod n>) mod n
a mod n = b mod n.

Unter der Voraussetzung das gilt (das sind jetzt nur ausgedachte Terme!):
(a + b/c - d^(1/5)) # (a + d/2)*f mod n
gilt dann auch:
((a + b/c - d^(1/5))) mod n = ((a + d/2)*f) mod n,
denn
<Term vor #> ist (a + b/c - d^(1/5)) und
<Term nach # ohne mod n> ist (a + d/2)*f.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> RSA Modulare Arithmetik
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2, 3  Weiter
Seite 1 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum