Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

RSA Modulare Arithmetik
Gehe zu Seite Zurück  1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> RSA Modulare Arithmetik
 
Autor Nachricht
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 24 Aug 2005 - 17:50:38    Titel:

Na wenn bei Deinen Betrachtungen allgemein m<n gilt, dann kannst Du Deine Rechnung benutzen.
Die Rechenregeln sind halt grad die Kongruenzen. Sie sagen ob zwei Terme bis auf die Restklassenrechnung gleich sind.
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 24 Aug 2005 - 18:09:40    Titel:

Tut mir leid, aber ich kapier das nicht... Wie kann ich denn die Rechenregeln für Kongruenzen für Ausdrücke mit einem normalen "=" verwenden. Ich seh da irgendwie keinen Zusammenhang... Question
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 24 Aug 2005 - 18:19:31    Titel:

Na wenn da steht
a # b mod n
bedeutet das auch
a mod n = b mod n.
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 24 Aug 2005 - 18:45:55    Titel:

Nein, ich checks immer noch nich...

wenn gilt:

a # b mod n
c # d mod n

gilt demnach auch:

a mod n = b mod n
c mod n = d mod n

Es gilt auch:

a + c # (b + d) mod n [ Rechenregel für Addition ]

wie schreib ich denn das jetzt auf "=" um???
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 24 Aug 2005 - 18:50:29    Titel:

Das ist dann
(a+c) mod n = (b+d) mod n.

Für zwei Terme T1 und T2 ist
T1 # T2 mod n
gleichbedeutend zu
T1 mod n = T2 mod n,
egal ob die Terme einzelne Variablen oder durch Rechenzeichen verbundene Variablen und Zahlen sind.
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 24 Aug 2005 - 23:44:11    Titel:

Hä?? Ich checks einfach nich!

Beispiel:

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

Gilt das jetzt oder nicht und wannund wann nicht und woher weiss ich dass dann???

Wenn ich die Kongruenzen auf "=" umforme erhalte ich ja immer so was:

z.B. wenn a # b mod n --> a mod n = b mod n, dann hab ich aber keine Gleichung vom Typ x = y mod z, sondern immer x mod z = y mod z...

Aber vielen Dank für die Erklärungen schon mal...
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 25 Aug 2005 - 11:42:16    Titel:

Hiob hat folgendes geschrieben:
a mod n + b mod n = ( a + b ) mod n

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


Woher weiss ich das?

Und das mit dem Umformen von "#" versteh ich ja (danke für die ausführliche Erkärung), aber ich kann mir daraus keine erlaubten algebraischen Umformen ableiteten.

Wenn ich folgenden "Rechenregeln" aufstelle:

I. a mod n + b mod n = ( a + b ) mod n
II. a mod n * b mod n = ( a * b ) mod n
III. (a mod n ) ^ b = (a^b) mod n

Woher weiss ich, wann diese anwendbar sind?

Du sagst I. gilt wenn 0 <= a mod n + b mod n < n. Wie kommt man darauf, was hat das mit Kongruenzen zu tun und wann gelten die anderen Regeln. Mehr möchte ich gar nicht wissen...
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 25 Aug 2005 - 13:53:59    Titel:

Charge69 hat folgendes geschrieben:
Wenn ich folgenden "Rechenregeln" aufstelle:

I. a mod n + b mod n = ( a + b ) mod n
II. a mod n * b mod n = ( a * b ) mod n
III. (a mod n ) ^ b = (a^b) mod n

Woher weiss ich, wann diese anwendbar sind?

Du sagst I. gilt wenn 0 <= a mod n + b mod n < n. Wie kommt man darauf, was hat das mit Kongruenzen zu tun und wann gelten die anderen Regeln. Mehr möchte ich gar nicht wissen...


Modulo liefert Dir Restklassen. Wendest Du "mod n" auf eine ganze Zahl an, so erhältst Du ein Ergebnis, das größer gleich Null ist und kleiner n. Genauer: kleiner gleich n-1. "mod n" liefert n paarweise verschiedene Restklassen.

Z.B. kann dir "mod 9" auf eine ganze Zahl angewendet als Ergebnisse eine der natürlichen Zahlen von 0 bis 8 zurückgeben, "mod 4" gibt 0, 1, 2 oder 3 zurück und "mod 1" immer 0.
Die Anzahl der möglichen Ergebnisse ist also sehr beschränkt und jedenfalls endlich.

Anders sieht es mit den allgemeiner bekannten Rechenoperationen aus. "+", "-" und "*" angewendet auf ganze Zahlen können bei freier Wahl der Operanden jede mögliche ganze Zahl erzeugen.
Die Anzahl der möglichen Ergebnisse ist unbeschränkt.

Nun hast Du die möglichen Ergebnisse durch die Wahl Deiner Operanden schonmal eingeschränkt.

I. a mod n + b mod n = ( a + b ) mod n
Auf der rechten Seite ist Modulo die äußere (zuletzt angewandte) Rechenoperation (Addition ist die innere), daher weiß man, daß sich der Wert des Terms "( a + b ) mod n" zwischen 0 und n-1 befindet.
Auf der linken Seite ist Modulo die innere Rechenoperation und Addition die äußere. Man weiß, daß die Werte von "a mod n" und "b mod n" jeweils zwischen 0 und n-1 liegen. Daraus folgt, daß der Wert der gesamten linken Seite zwischen 0 und 2*(n-1) liegt.
Für n>1 ist aber 2*(n-1) größer gleich n. Deshalb kann es bei ungünstiger Wahl von a, b und n vorkommen, daß der Wert auf der linken Seite größer ist als der auf der rechten Seite. Also gilt die Gleichung nicht bzw. nur beschränkt.
Und diese Beschränkung ist genau das, was einem günstige a, b und n verspricht.
"0 <= a mod n + b mod n < n" liefert nur solche a, b und n, für die die Gleichung
a mod n + b mod n = ( a + b ) mod n
gilt.
Charge69
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.07.2005
Beiträge: 33

BeitragVerfasst am: 25 Aug 2005 - 14:22:45    Titel:

I. a mod n + b mod n = ( a + b ) mod n für 0 <= a mod n + b mod n <= n-1

II. a mod n * b mod n = ( a * b ) mod n für 0 <= a mod n * b mod n <= n-1

III. (a mod n ) ^ b = (a^b) mod n für 0 <= (a mod n ) ^ b <= n-1

Sind dann diese Geleichung mit den entsprechenden Einschränkungen korrekt?

Es käme ja nur zu "Fehlern", wenn der linke Teil größer ist als n-1, da die rechte Seite definitionsgemäß kleiner n sein muss oder?
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.05.2005
Beiträge: 1379

BeitragVerfasst am: 25 Aug 2005 - 14:30:38    Titel:

Genau.

Bei III. braucht man noch als Nebenbedingung, daß (a mod n) ^ b eine ganze Zahl ist. Das kann man implizieren, indem man b>=0 als Bedingung hinzufügt.
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 Zurück  1, 2, 3  Weiter
Seite 2 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