Computing very large exponents in python

Question

I am currently simulating my cryptographic scheme to verify it. I developed the code, but I was stuck in one place.

I'm trying to take: g**x where

 g = 256 bit number x = 256 bit number 

Python hangs at this stage, I read a lot of forums, etcc threads, but came to the conclusion that python hangs because it is difficult to handle such large numbers.

any idea how to do this? any two lines of code, any library, everything that can be done.

Answer 1

It is not hanging, it is just processing. This will ultimately give you an answer if it has not exhausted memory at first.

I have not heard about the result of such a process, which is used in cryptography; as a rule, the modulus of the indicated power matters. If this is the same in your case, you can simply use the pow() 3-argument form.

Answer 2

You should not try to calculate x ^ y directly for huge y values ​​- as already indicated, this is quite difficult to do (it takes a lot of space and processing power). You need to look at the algorithms that solve the problem for you, with fewer multiplication operations. Take a look at: http://en.wikipedia.org/wiki/Exponentiation_by_squaring for starters.

Modular exponentiation is also well understood: http://en.wikipedia.org/wiki/Modular_exponentiation .

You will need to use the python library for large numbers, e.g. http://gmpy.sourceforge.net/ .

If that helps, I did a modular exponentiation with mpir . I will attach this code, you will need to convert it to python, of course.

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

Answer 3

I'm not quite sure that you value the absolute value of what you ask for Python. Bringing something to power x , where x is 256 bits long, does the equivalent of 2 ** 256 multiplications or 115792089237316195423570985008687907853269984665640564039457584007913129639936 multiplication. As you can imagine, this may take some time. And the space that I guarantee you is not enough.