Fun-Soft - Programmierforum

Autor

Thread - Seiten: [ 1 ] > 2 <

010
07.07.2003, 19:41 Uhr
~0xdeadbeef
Gast

Du willst RSA machen, was? Einfacher Trick:

a^b mod n = (a mod n)^b mod n

Also ist zum Beispiel

a^3 mod n = (a mod n) * (a mod n) * (a mod n)

woraus sich folgender C-Code ableitet:

C++:

int pow_mod(int basis, int exponent, int divisor) {
    int ergebnis = 1;
    while(exponent) {
        /* schnelles potenzieren, in O(log(n)) */
        if(exponent%2) {
            ergebnis = (ergebnis * (basis % divisor))%divisor;
            --exponent;
        } else {
            ergebnis = (ergebnis * ergebnis) % divisor;
            exponent /= 2;
        }
    }
    return ergebnis;
}

Jedenfalls im Prinzip, den Code hab ich nur grad mal so hingekladdet.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

011
07.07.2003, 20:39 Uhr
ao

(Operator)

@deadbeef: Nicht übel, das. Hast du nen Link parat, der die Theorie dazu erklärt?

@Uli: Als Übungsaufgabe machst du das Ganze in Rekursiv, ja? ;-)

ao

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

012
08.07.2003, 10:54 Uhr
~0xdeadbeef
Gast

Es liegt ganz einfach daran, dass Z mod n für jedes n aus N ein Ring (wenn n prim ist, sogar ein Körper) und die Gleichheit modulo n eine Äquivalenzrelation auf Z ist. Dementsprechend ist

Code:

a = (a % c) mod c
b = (b % c) mod c

und dementsprechend

C++:

a * b = (a % c) * (b % c) mod c

woraus sich der Rest ergibt.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

013
08.07.2003, 11:32 Uhr
ao

(Operator)

Ach ja, natürlich. Wie konnte ich das nur übersehen. ;-)

ao

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

014
08.07.2003, 19:41 Uhr
~Uli
Gast

Ja Hallo,

nicht schlecht. Es geht echt um das RSA. Wir machen untersuchungen am RSA an der Hochschule und dafür will ich ein Programm schreiben um das ganze einfacher zu gestalten.

@deadbeef: ich werde denn Code erst einmal setzen lassen. Aber da scheitn was dran zu sein. Muß jetzt erst einmal ein paar Prüfungen schreiben und danach geht es weiter mit dem Prog. Aber danke schon erst einmal.

Bye deUli

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: [ 1 ] > 2 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: