在python中计算非常大的指数

Question

目前我正在模拟我的加密方案来测试它.我已经开发了代码,但我一度陷入困境.

我想采取:g**x 在哪里

g = 256 bit number
x = 256 bit number

Python挂起了这一点,我已经阅读了很多论坛,线程等,但只得出结论python挂起,因为它很难处理这么大的数字.

任何想法怎么做？任何两行代码,任何库,任何可以完成的事情.

Answer 1

它不是悬挂,它只是处理.这将最终给你答案,只要它不出来的内存中运行第一.

我没有听说过这种过程在密码学中使用的结果; 通常,重要的是所述功率的模数.如果它在你的情况下是相同的,那么你可以只使用3参数形式pow().

Answer 2

您不应该尝试直接计算x ^ y以获得巨大的y值 - 正如已经指出的那样,这很难做到(占用大量空间和处理能力).您需要查看使用较少乘法运算为您解决问题的算法.请看一下:http://en.wikipedia.org/wiki/Exponentiation_by_squaring为初学者.

模块化取幂也很清楚:http://en.wikipedia.org/wiki/Modular_exponentiation.

您将需要使用python库来处理大数字,例如http://gmpy.sourceforge.net/.

如果有任何帮助,我使用mpir在C中进行模幂运算.我会附上那段代码,当然你需要把它转换成python.

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

我不太确定你是否欣赏你要求Python做的事情.将某些东西提升到256位长的功率x,x相当于2**256次乘法,或115792089237316195428470985008687907853269984665640564039457584007913129639936乘法.你可以想象,这可能需要一些时间.和空间,我保证你没有足够的空间.