在Python中计算超大指数

Question

目前我正在模拟我的加密方案来进行测试。我已经写好了代码，但在某个地方遇到了瓶颈。

我想计算：g**x，其中

g = 256 bit number
x = 256 bit number

在这个地方，Python程序卡住了。我查阅了很多论坛和讨论，但最终得出的结论是，Python处理这么大的数字时很困难，所以它就挂住了。

有没有什么办法可以解决这个问题？比如两行代码、某个库，或者其他任何可以尝试的方法。

Answer 1

我不太确定你是否意识到你让Python做的事情有多复杂。把一个数提升到一个256位长的指数x，就相当于要进行2的256次方的乘法，也就是要进行115792089237316195423570985008687907853269984665640564039457584007913129639936次乘法。你可以想象，这会花费不少时间。而且，这需要的空间，我敢保证你是没有足够的。

Answer 2

你不应该直接计算很大的y值的x^y，因为这样做非常困难（需要很多空间和处理能力）。你需要找一些算法，能用更少的乘法运算来解决这个问题。可以先看看这个链接：http://en.wikipedia.org/wiki/Exponentiation_by_squaring。

关于模幂运算也有很多成熟的理解，可以参考这个链接：http://en.wikipedia.org/wiki/Modular_exponentiation。

如果你需要处理大数字，可以使用一个Python库，比如http://gmpy.sourceforge.net/。

如果对你有帮助，我在C语言中用mpir做过模幂运算。我会附上那段代码，你当然需要把它转换成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

它并不是卡住了，只是在处理数据。它最终会给你答案，只要它没有先耗尽内存。

不过，我没听说过这种处理结果在加密学中被使用；通常情况下，重要的是这个幂的模。如果在你的情况也是这样，那你可以直接使用pow()的三参数形式。