Berechnung sehr großer Exponenten in Python

Question

Derzeit simuliere ich mein kryptographisches Schema, um es zu testen. Ich habe den Code entwickelt, aber ich stecke an einem Punkt fest.

ich zu nehmen versuche: g**x wo

g = 256 bit number 
x = 256 bit number 

Python an dieser Stelle hängt, habe ich eine Menge von Foren gelesen, Themen etcc aber nur zu dem Schluss kommen, dass Python hängt, wie es ist schwer für sie um so große Zahlen zu verarbeiten.

eine Idee, wie kann es getan werden? irgendein zweizeiliges Stück Code, irgendeine Bibliothek, alles, was getan werden kann.

Answer 1

Es hängt nicht, es ist nur Verarbeitung. Es gibt wird schließlich geben Sie die Antwort, vorausgesetzt, es wird nicht aus Speicher zuerst ausgeführt.

Ich habe noch nicht von dem Ergebnis eines solchen Prozesses in der Kryptographie verwendet gehört; normalerweise ist es der Modul der besagten Macht, der zählt. Wenn es in Ihrem Fall dasselbe ist, können Sie stattdessen das 3-Argumente-Formular von pow() verwenden.

Answer 2

Ich bin mir nicht ganz sicher, ob Sie die schiere Größe von Python zu schätzen wissen. Wenn man etwas auf eine Potenz x anhebt, wo x 256 Bits lang ist, macht es das Äquivalent von 2 ** 256 Multiplikationen oder 115792089237316195423570985008687907853269984665640564039457584007913129639936 Multiplikationen. Wie Sie sich vorstellen können, kann dies einige Zeit dauern. Und Platz, von dem ich garantiere, dass du nicht genug davon hast.

Answer 3

Sie sollten nicht versuchen, x^y direkt für riesige Werte von y zu berechnen - wie bereits erwähnt wurde, ist das ziemlich schwierig (erfordert viel Platz und Rechenleistung). Sie müssen nach Algorithmen suchen, die das Problem mit weniger Multiplikationsoperationen lösen. Werfen Sie einen Blick auf: http://en.wikipedia.org/wiki/Exponentiation_by_squaring für den Anfang.

Modulare Exponentiation ist auch ziemlich gut verstanden: http://en.wikipedia.org/wiki/Modular_exponentiation.

Sie müssen eine Python-Bibliothek für große Zahlen verwenden, z. B. .

Wenn es irgendeine Hilfe ist, habe ich modulare Exponentiation in C mit mpir. Ich werde diesen Code anhängen, Sie müssen ihn natürlich in Python konvertieren.

int power_modn(mpz_t c, mpz_t b, mpz_t e, mpz_t n) 
{ 
     mpz_t result; 
     mpz_t one; 
     mpz_t r; 

     mpz_t modulus; mpz_t exponent; mpz_t base; 

     mpz_init(modulus); mpz_init(exponent); mpz_init(base); 
     mpz_init(result); mpz_init(one); mpz_init(r); 

     mpz_set_ui(result, 1); 
     mpz_set_ui(one, 1); 

     mpz_set(base, b); 
     mpz_set(exponent, e); 
     mpz_set(modulus, n); 

     while (mpz_cmp_ui(exponent, 0) > 0) 
     { 
       if (mpz_mod_ui(r, exponent, 2) == 1) 
       { 
         mpz_mul(result, result, base); 
         mpz_mod(result, result, modulus); 
       }; 
       mpz_mul(base, base, base); 
       mpz_mod(base, base, modulus); 
       mpz_fdiv_q_ui(exponent, exponent, 2); 
     } 

     mpz_set(c, result); 
    return 0; 
}