a hoch b mod c Algorithmus für große Zahlen?

B4ndit

Hallo,

ich bin auf der Suche nach einem Algorithmus der a hoch b mod c berechnet, aber dies mit großen Zahlen, also mit Zahlen die mehr als hundert Stellen haben.

Kennt da wer einen, vielleicht sogar mit Pseudocode-Implementierung?

SeppJ

Soll das ^ ein XOR sein oder ein Exponent? Falls Exponent (RSA?), dann nennt sich das Modular Exponentiation. Es gibt mehrere Algorithmen, die du unter dem Stichwort findest. Falls das für RSA sein sollte, dann sollte das aber eigentlich in jeder ernsthaften Erklärung des Verfahrens erwähnt werden.

DarkShadow44

Schau dir mal diese BigInteger Klasse für C# an, ist gut kommentiert mit ausführlicher Erklärung.

B4ndit

Danke für die Hilfe, ja es ist für eine eigene RSA-Implementierung. Ich habe 4 Monate Freizeit bis zu meinem nächsten Job, also suche ich was um die Langeweile zu überbrücken.

SeppJ

DarkShadow44 schrieb:

Schau dir mal diese BigInteger Klasse für C# an, ist gut kommentiert mit ausführlicher Erklärung.

Nee, 165^6874765387465378653785637856783653786458986094586978983[... 700 weitere Stellen ... ]49748546487346387 mod 7348465783473492373957378563487647833793229732[...ähnlich lang ...]4377489437503

berechnen wir nicht explizit. Auch nicht mit einer Bigintegerklasse. edit: Ach, sie kann modular Exponentiation. Dann ist das natürlich was anderes

B4ndit

Danke, dann dürfte ja sowas hier reichen:

unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
    unsigned long long test;
    unsigned long long n = num;
    for(test = 1; pow; pow >>= 1)
    {
        if (pow & 1)
            test = ((test % mod) * (n % mod)) % mod;
        n = ((n % mod) * (n % mod)) % mod;
    }

    return test; /* note this is potentially lossy */
}

int main(int argc, char* argv[])
{

    /* (2 ^ 168277) % 673109 */
    printf("%u\n", mod_pow(2, 168277, 673109));
    return 0;
}

Oder doch nicht, da ja m in diesen Fallen das RSA-Modul ist und einige hundert Stellen hat. Mit Restklassen und Kongruenz kenne ich mich leider wenig aus um da mathematisch jetzt was selbst zu machen. Ich möchte eigentlich nur selbst implementieren, so zum Spaß.

SeppJ

Ja, du brauchst schon irgendeinen komplexeren Datentyp um die Zahlen selbst darzustellen. BigInt und Co. sind da schon gut. Aber mit solchen Bibliotheken musst du eben auch ein cleveres Verfahren für modulo Potenzen anwenden, selbst wenn es verlockend ist, damit wirklich erst die Potenz auszurechnen und dann zu teilen. Da rechnest du dich sonst tot. Ich hatte irrtümlich gedacht, DarkShadow44 wolle darauf hinaus. Aber er hat Recht, dass solche Bibliotheken oft bereits fertige Algorithmen dafür bieten, da sie genau wissen, dass die Benutzer häufig RSA damit programmieren wollen.

Wenn der verlinkte Benchmark stimmt und wir mal annehmen, dass die Version 1.0 eine naive Implementierung des Verfahrens ist, dann scheint man auch noch gewaltig viel rausholen zu können, wenn man genauer über die Implementierung nachdenkt. Oder eben die fertige Lösung benutzen. Aber das ist ja weniger spannend und hier wohl nicht gewünscht .

B4ndit

Ja, es geht mir schon um den Weg und mir ist klar, dass ich da immer meilenweit von einer effektiven Implementierungen, der dafür spezialisierten, Libs entfernt bin. Manchmal will man halt selbst kochen, auch wenn es Spitzenkochs viel besser können. Es ist halt der Ehrgeiz, was wirklich selbst zu machen, es muss wie bei selbst gebauten Möbeln oder elektronischen Schaltungen nicht perfekt sein. Sehr viele Menschen machen Sachen selbst, die es schon viel viel besser gibt. Würde dies nicht so sein, würde es sicherlich kaum Hobby geben. Und aus anfangs Hobbyprojekte ist schon viel entstanden in dieser Welt.

Vor allem habe ich ja jetzt Freizeit ohne Ende, solche Zeiten gönne ich mir immer mal alle 2-3 Jahre. Ich lebe recht bescheiden und bin daher nie auf einen bestimmten Job angewiesen, diese Freiheit wollte ich immer so haben. Aber das ist jetzt vom Thema weg.

Also, wem noch gute Algorithmen rund um RSA einfallen, dann immer her damit. Sie müssen nicht die schnellsten sein, sondern sich eher schnell implementieren lassen, aber trotzdem nicht nun in der O-Notation einen Fakultät drin stehen haben^^. Der Schönhage Strassen Algorithmus ist zwar schneller wie der Karatsuba, aber für mich nicht zu verstehen und was ich nicht verstehe, will ich auch nicht implementieren.

otze

dann implementiere karatsuba und dann square & multiply für die mod-exponentiation.

...ich kenne noch einen netten alten handschriftlichen "Algorithmus" und ich bin bei solchen Sachen immer so froh, dass ich ein wenig Assembler kann. In neueren Bitwelten gibt es 64 Bit, 128 Bit, 256 Bit...das ist schon oft mehr als genug, um bequem mit Integern zu arbeiten, aber das ist natürlich nicht der Punkt (eher 8Bit-Welten?). Auch nicht der, dass es nette Sprachen und Dokumentationen für solchen Kram gibt (ich denke an Fortran und Haskell aber auch java und python werden ja in alle möglichen Richtungen gehypt).

Ganz nebenbei würde ich gewisse freie Zeit auch dazu nutzen, schwierige Algos besser zu verstehen. Was ist genau das wichtigste Hindernis zu verstehen?
( http://malte-leip.net/beschreibung_ssa.pdf bringt nicht weiter?)
oder http://stackoverflow.com/questions/1184296/why-can-haskell-handle-very-large-numbers-easily
oder
http://pajhome.org.uk/crypt/rsa/implementation.html

Letztlich hilft doch gerade die Auseinandersetzung mit solchen Problemen, beim Programmieren schneller auf Lösungen zu kommen.
Denkweisen wie "meilenweit entfernt" übertreiben, sind meist nicht stimmig und dienen wozu?

B4ndit

Danke für die Links. Ja du hast Recht sich wirklich mit dem Algo auseinanderzusetzen hilft. Faltungen und Fourier-reihen hatte ich mir noch nie angeschaut und deswegen den Strassen Algo erst einmal aus meiner Liste gestrichen. Dein verlinktes Script dazu sieht aber sehr gut aus.

Ich werde mich als erstes dem karatsuba widmen.

Es gibt ja viele Blog, Scripte etc. über RSA aber so eine richtige schöne Anleitung von vorne bis hinten habe ich nicht gefunden. Irgendwas fehlt immer. Also, selbst ist der Mann.