21 replies to this topic

[-Alex-]

Also...

Wie kann ich multiplikative Inversen mit dem erweiterten euklidischen Algorithmus berechnen? Die Implementation des "normalen" euklidischen Algorithmus ist relativ einfach, der erweiterte stellt da schon eher Probleme dar.

Ist m eine positive ganze Zahl und a eine zu m teilerfremde Zahl, so gibt es eine ganze Zahl i mit 0 <= i <= m-1, sodass  
i * a = 1 (mod m) gilt.  

i ist eben die besagte multiplikative Inverse, die es zu berechen gilt.

Bei großen Zahlen ist das mit Papier und Bleistift zu zeitaufwendig, deshalb benötige ich Automatisierung


Wenn jemand ne Idee hat oder bei Google was findet bitte hier hinein. Wäre sehr nett

[Bazz-Dee]

Der erweiterte euklidische Algorithmus ist eine Erweiterung des euklidischen Algorithmus. Die Eingabe besteht aus zwei Zahlen a und b und der Algorithmus liefert den größten gemeinsamen Teiler d sowie zwei ganze Zahlen s und t mit d = s * a + t * b und liefert damit einen konstruktiven Beweis für das Lemma von Bézout.







Die Darstellung als Linearkombination (selten auch Vielfachsummendarstellung genannt) d = s * a + t * b ist besonders nützlich, wenn a und b teilerfremd sind, d. h. ggT(a,b) = 1. In diesem Fall ist d = 1 und s ist das multiplikative Inverse von a modulo b.

[P. Stylez]

Nur mal zum Verständnis...

a ist keine ganze zahl, oder?

Weil 1 % m (m aus Z) ist bei mir entweder 0 oder 1

Und was soll jetzt der Input des Programms sein?

[Bazz-Dee]

Nur mal zum Verständnis...

a ist keine ganze zahl, oder?

Weil 1 % m (m aus Z) ist bei mir entweder 0 oder 1

Und was soll jetzt der Input des Programms sein?

ich denke mal er will i heraus bekommen, also wird er a eingeben, ob m nun auch eingabe oder ne konstante ist weiss ich nciht.

[-Alex-]

Nur mal zum Verständnis...

a ist keine ganze zahl, oder?

Weil 1 % m (m aus Z) ist bei mir entweder 0 oder 1

Und was soll jetzt der Input des Programms sein?

ich denke mal er will i heraus bekommen, also wird er a eingeben, ob m nun auch eingabe oder ne konstante ist weiss ich nciht.

Ich will sowohl a als auch m eingeben, ich kann euch auch direkt aufklären: Es darum den privaten Schlüssel im RSA Algorithmus zu berechnen. Leider gibt es da ein Problem:
Ich bin derzeit Schüler und hab kein Informatik, d.h. alles das, was ich "kann", hab ich mir mehr oder weniger selbst beigebracht und das reicht nicht aus. Vom zahlentheoretsichen Verständnis ist mir alles klar eben nur an der Implementatuion hapert's.

[P. Stylez]

Was ist denn jetzt a ?

Ich hab doch recht, dass bei der Modulo-Operation nur 0 oder 1 rauskommen kann, oder hab ich das 1 (mod m) falsch gedeutet?

a mod b = a - [a/b]*b

wobei [a/b] die nächste ganze zahl <= a/b ist.

[Bazz-Dee]

Schreib mal ganz genau auf was du mit Bleistift auf Papier rechnest, in welcher Reihenfolge und so, vielleicht versteh ichs dann besser.


edit:
hilft das weiter?
http://www.linux-mag...to/krypto4.html

[-Alex-]

Was ist denn jetzt a ?  /public/style_emoticons/default/lol.gif...  

Ich hab doch recht, dass bei der Modulo-Operation nur 0 oder 1 rauskommen kann, oder hab ich das 1 (mod m) falsch gedeutet?

a mod b = a - [a/b]*b

wobei [a/b] die nächste ganze zahl <= a/b ist.

Sry... a ist aus der Menge der ganzen Zahlen außer 0.

Also die multiplikative Inverse ist diejenige Zahl, die bei der Multiplikation das Ergebnis 1 ergibt bezüglich einem Modulus.

z.B. hier was einfaches: 4 * i (mod 5) = 1


Logisch kommt i = 4 raus, denn 4*4 = 16
und 16 mod 5 = 1 somit ist die Gleichung erfüllt.

[Bazz-Dee]

und er soll alle möglichen i ausgeben ja ?



long i = 0;
long a = 25;
long m = 5;

while (i < maximum von long) {
if (((a * i) mod m) == 1) {
std::cout << i;
}
i++;
}



???

[P. Stylez]

int a, m;



// a einlesen

cout << "Bitte a eingeben: ";

a << cin;



// m einlesen

cout << "Jetzt bitte m eingeben: ";

m << cin;



// Fehlerfreie Eingabe wird vorausgesetzt

// ggf. Fehler abfangen



int i;



for( i = 0; i <= m-1; i++ ){

  if( a*i % m == 1 ) break;

}



cout << "Das Ergebnis lautet i = " << i;

So in etwa..?

[Bazz-Dee]

aaah jetz wo ich p.stylez code sehe versteh ich des

[-Alex-]

Ich liebe euch!


Ja der Code von P. Stylez funzt


Vielen Dank

[P. Stylez]

Benutz aber statt der "int" lieber "long" wie Bazz es gemacht hat, für den Fall dass Du richtig lange Zahlen einlesen willst.

[Synthor]

wow!

bin grad echt mal perplex
nie gewusst, dass hier die hardtechnojungs soviel plan vom coden haben.

das find ich gut!
bin irgendwie vom vorurteil geplagt, dass alle hardtekker mit großen puppies und sonst auch total verballert rumrennen....ach vorurteile sind scheisse

[Josh Revilo]

int und long sind gleich lang auf 32bit systemen
würd da eher unsigned int vorschlagen, dann haste doppelt soviel positive zahlen, oder long long/_int64, das is aber nich standardisiert

[P. Stylez]

int und long sind gleich lang auf 32bit systemen  /public/style_emoticons/default/p.gif...

Stimmt, da geb ich Dir Recht

Allerdings muss ich dazu sagen, dass ich seit gut nem Jahr nicht mehr in C++ programmiert hab, sondern fast nur noch in Java und R. Und in Java sind long Variablen 64 Bit Ganzahl-Werte

[Josh Revilo]

Was du codest in R und hast dich noch nicht erschossen? Ja gut, für Statistik sachen ist R wohl optimal... Was, du machst Statistik und hast dich noch nicht erschossen?

[Bazz-Dee]

oh ja, ich hab da als java mensch auch nciht so dran gedacht

[P. Stylez]

Was du codest in R und hast dich noch nicht erschossen?  /public/style_emoticons/default/o.gif... Ja gut, für Statistik sachen ist R wohl optimal... Was, du machst Statistik und hast dich noch nicht erschossen?  /public/style_emoticons/default/o.gif...  /public/style_emoticons/default/d.gif...

Diplomarbeit

Is eigentlich gar nicht mal so verkehrt die Sprache, obwohl man sich teilweise echt umstellen muss...

Wobei ich mich allerdings beinahe erschossen hätte ist die Kombination von R und Tcl/Tk. Das hat mich in den letzten 6 Monaten schon so manches graue Haar gekostet.

[Josh Revilo]

die Kombination von R und Tcl/Tk

sounds lovely. was istn das thema wenn man fragen darf?

[P. Stylez]

(Langsam wird's echt Offtopic *gg*)

Das Ding schimpft sich "Untersuchung und Implementierung sp ezieller statistischer Testverfahren der Changepoint Analyse".
Verlang jetzt aber bitte nicht von mir Dir in zwei Zeilen zu erklären, was ein Changepoint ist

[Josh Revilo]

Ich hatte sowas ähnliches als Seminarthema. Wir sollten ein theoretisches Analyseverfahren verifizieren mit R, ich hab weder Plan von Statistik noch von R, das war die Hölle sach ich dir. Daher meine leichte Abneigung