Calculando muy grandes exponentes en Python

Question

Actualmente Estoy simulando mi esquema criptográfico para probarlo. He desarrollado el código, pero estoy atascado en un punto.

estoy tratando de tomar: g**x donde

g = 256 bit number 
x = 256 bit number 

Python cuelga en este punto, he leído un montón de foros, discusiones ETCC pero sólo llegado a la conclusión de que se cuelga pitón, como es difícil para él para procesar números tan grandes

alguna idea de cómo se puede hacer esto? cualquier código de dos líneas, cualquier biblioteca, cualquier cosa que se pueda hacer.

Answer 1

No está colgado, es sólo el procesamiento. Se le tiempo le dará la respuesta, siempre y cuando no se ejecuta fuera de la memoria en primer lugar.

No he oído hablar del resultado de tal proceso siendo usado en criptografía; usualmente es el módulo de dicho poder lo que importa. Si es lo mismo en su caso, puede usar la forma de 3 argumentos de pow().

Answer 2

no estoy muy seguro de que usted aprecia la magnitud de lo que está pidiendo Python a hacer. Elevar algo a una potencia x donde x tiene 256 bits de longitud, está haciendo el equivalente a 2 ** 256 multiplicaciones o 115792089237316195423570985008687907853269984665640564039457584007913129639936 multiplicaciones. Como se puede imaginar, esto puede llevar algo de tiempo. Y espacio, que te garantizo que no tienes suficiente.

Answer 3

No intente calcular x^y directamente para valores enormes de y, como ya se ha señalado, esto es bastante difícil de hacer (requiere mucho espacio y potencia de procesamiento). Debe analizar los algoritmos que resuelven el problema por usted con menos operaciones de multiplicación. Eche un vistazo a: http://en.wikipedia.org/wiki/Exponentiation_by_squaring para empezar.

La exponenciación modular también se comprende bastante bien: http://en.wikipedia.org/wiki/Modular_exponentiation.

Deberá utilizar una biblioteca de Python para números grandes, como http://gmpy.sourceforge.net/.

Si es de alguna ayuda, hice la exponenciación modular en C usando mpir. Adjuntaré ese código, necesitarás convertirlo a python, por supuesto.

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