Eine überlegung bezüglich einer Modulofunktion, ist das richtig?

14.03.2006, 18:49	Löli	Auf diesen Beitrag antworten »
Eine überlegung bezüglich einer Modulofunktion, ist das richtig? Hallo! Ich habe folgende Ausgangsgleichung: c = (km) mod n Dabei sind alle Variablen Elemente der natürlichen Zahlen. Es gilt außerdem: 0 kleiner gleich m kleiner gleich n 1 kleiner gleich k kleiner gleich n Außerdem muss der größte gemeinsame Teiler aus k und n gleich 1 sein. Das ist deshalb so, weil das ganze eigendlich eine Verschlüsslungsfunktion darstellen soll, wo eine eindeutige Zuordnung erfolgt. Warum der Teiler aus k und n gleich 1 sein muss, hab ich schon bewiesen. So, jetzt wollte ich eine Weg finden, wie ich aus c wieder m erhalte. Dazu habe ich folgende Überlegungen geschrieben: Für eine normale Rechnung gilt: m a = c c * a^(-1) = m Dabei ist a^(-1) zu a invers. Da die Funktion c = (m * t) mod n gilt, wird nun wie oben ein Inverses x zu k mod n gesucht, mit dem die Rechnung ebenso rückgängig gemacht werden kann: Weil a * a^(-1) = 1 gilt, soll für k * x auch gelten: x * k ist kongruent zu 1 mod n ( = 1 ) Für x * k wird also vorausgesetzt, dass es der Form qn + 1 entspricht, damit die rechte Seite der Gleichung gilt: x k = qn + 1 Stellt man nun noch nach x um, erhält man: x = (qn + 1) / k = (n + 1) / k (Vereinfachung) Ich weiß, dass die Rechnung so stimmt, aber ist an meinen Überlegungen von euch aus gesehen irgendetwas unklar oder unvollständig? Vielen Dank für Hilfe.
14.03.2006, 19:04	Löli	Auf diesen Beitrag antworten »
Entschuldigt bitte, aber ich habe selbst bemerkt, dass es noch einen kleinen Fehler gibt: X ergibt nicht zwangsläufig eine ganze Zahl, wie bei dem Beispiel k = 5 und n = 26, obwohl ggT(5, 26) = 1 gilt. Das heißt, es muss ein entsprechendes q gesucht werden, sodass es irgendein Vielfaches von 26 gibt, was addiert mit 1 durch 5 teilbar ist. Mit anderen Worten soll gelten: (qn + 1) = k * p qn = p*k - 1 Aber wie mach ich nun weiter? Wie finde ich ein Vielfaches von n, was irgendeinem Vielfachen von k, subtrahiert mit 1 entspricht?
14.03.2006, 20:26	AD	Auf diesen Beitrag antworten »
Benutze den EEA (erweiterter euklidischer Algorithmus) für $\begin{eqnarray} k \end{eqnarray}$ und $\begin{eqnarray} n \end{eqnarray}$ : Der liefert dir ganze Zahlen $\begin{eqnarray} a,b \end{eqnarray}$ mit der Eigenschaft $\begin{eqnarray} ak+bn = \mathrm{ggT}(k,n) = 1 \end{eqnarray}$ Jetzt nur noch das ganze mit c multiplizieren liefert $\begin{eqnarray} cak \equiv c\mod n \end{eqnarray}$ , d.h. $\begin{eqnarray} m=ca\mod n \end{eqnarray}$ ist deine gesuchte Lösung.
14.03.2006, 20:32	Löli	Auf diesen Beitrag antworten »
Vielen Dank, Arthur! Ich glaubte erst auf dem Weg ne genaue allgemeine Lösung zu finden, aber da scheint der EEA wohl das einzige zu sein, was hilft...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »