Calcul de très grands exposants en python

Question

Actuellement, je simule mon schéma cryptographique pour le tester. J'ai développé le code mais je suis coincé à un moment donné.

Je suis en train de prendre: g**x où

g = 256 bit number 
x = 256 bit number 

Python est suspendu à ce point, j'ai lu beaucoup de forums, discussions ETCC mais seulement arriver à la conclusion que bloque python, comme il est difficile pour elle pour traiter de si grands nombres.

aucune idée comment cela peut-il être fait? n'importe quelle ligne de code, n'importe quelle bibliothèque, tout ce qui peut être fait.

Answer 1

Ce n'est pas suspendu, c'est juste un traitement. Il éventuellement vous donner la réponse, à condition qu'il ne manque pas de mémoire en premier.

Je n'ai pas entendu parler du résultat d'un tel processus utilisé dans la cryptographie; c'est généralement le module de la puissance qui compte. Si c'est la même chose dans votre cas, vous pouvez simplement utiliser le formulaire à 3 arguments de pow() à la place.

Answer 2

Je ne suis pas sûr que vous appréciez l'ampleur de ce que vous demandez à Python de faire. Élever quelque chose à une puissance x où x est 256 bits de long, fait l'équivalent de 2 ** 256 multiplications, ou 115792089237316195423570985008687907853269984665640564039457584007913129639936 multiplications. Comme vous pouvez l'imaginer, cela peut prendre du temps. Et l'espace, dont je vous garantis que vous n'en avez pas assez.

Answer 3

Vous ne devriez pas essayer de calculer x^y directement pour des valeurs énormes de y - comme cela a déjà été souligné, c'est assez difficile à faire (il faut beaucoup d'espace et de puissance de traitement). Vous devez examiner les algorithmes qui résolvent le problème avec moins d'opérations de multiplication. Jetez un oeil à: http://en.wikipedia.org/wiki/Exponentiation_by_squaring pour les débutants. L'exponentiation modulaire est également assez bien comprise: http://en.wikipedia.org/wiki/Modular_exponentiation.

Vous devrez utiliser une bibliothèque python pour les grands nombres, par exemple http://gmpy.sourceforge.net/.

Si c'est de l'aide, j'ai fait l'exponentiation modulaire en C en utilisant mpir. Je vais attacher ce code, vous devrez le convertir en python bien sûr.

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; 
}