python 在python中计算非常大的指数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2392235/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Calculating very large exponents in python
提问by miraclesoul
Currently i am simulating my cryptographic scheme to test it. I have developed the code but i am stuck at one point.
目前我正在模拟我的加密方案来测试它。我已经开发了代码，但有一点被卡住了。
I am trying to take: g**xwhere
我试图采取：g**x哪里
g = 256 bit number
x = 256 bit number
Python hangs at this point, i have read alot of forums, threads etcc but only come to the conclusion that python hangs, as its hard for it to process such large numbers.
Python 在这一点上挂起，我已经阅读了很多论坛、线程等，但只能得出 Python 挂起的结论，因为它很难处理如此大的数字。
any idea how can it be done? any two line piece of code, any library, anything that can be done.
知道怎么做吗？任何两行代码，任何库，任何可以做的事情。
回答by Ignacio Vazquez-Abrams
It's not hanging, it's just processing. It willeventually give you the answer, provided it doesn't run out of memory first.
它不是挂起，它只是处理。这将最终给你答案，只要它不内存用完第一。
I haven't heard of the result of such a process being used in cryptography though; usually it's the modulus of said power that matters. If it's the same in your case then you can just use the 3-argument form of pow()instead.
不过，我还没有听说过在密码学中使用这种过程的结果；通常，重要的是所述功率的模数。如果您的情况相同，那么您可以使用 3 参数形式pow()代替。
回答by Ignacio Vazquez-Abrams
You shouldn't try to calculate x^y directly for huge values of y - as has already been pointed out, this is pretty difficult to do (takes lots of space and processing power). You need to look at algorithms that solve the problem for you with fewer multiplication operations. Take a look at: http://en.wikipedia.org/wiki/Exponentiation_by_squaringfor starters.
您不应该尝试直接计算 y 的巨大值的 x^y - 正如已经指出的那样，这很难做到（需要大量空间和处理能力）。您需要查看能够以较少的乘法运算为您解决问题的算法。看看：http: //en.wikipedia.org/wiki/Exponentiation_by_squaring初学者。
Modular exponentiation is also pretty well understood: http://en.wikipedia.org/wiki/Modular_exponentiation.
模幂也很好理解：http: //en.wikipedia.org/wiki/Modular_exponentiation。
You will need to use a python library for large numbers, such as http://gmpy.sourceforge.net/.
对于大数，您需要使用 python 库，例如http://gmpy.sourceforge.net/。
If it's any help, I did modular exponentiation in C using mpir. I'll attach that code, you'll need to convert it to python of course.
如果有任何帮助，我使用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;
}
回答by Greg Hewgill
I'm not quite sure you appreciate the sheer magnitude of what you're asking Python to do. Raising something to a power xwhere xis 256 bits long, is doing the equivalent of 2**256 multiplications, or 115792089237316195423570985008687907853269984665640564039457584007913129639936 multiplications. As you can imagine, this may take some time. And space, which I guarantee you don't have enough of.
我不太确定你是否理解你要求 Python 做的事情的巨大程度。将某事物提高到256 位长的幂x，x相当于进行 2**256 次乘法，或 115792089237316195423570985008687907853269984665640564039457584930736 可以想象，这可能需要一些时间。还有空间，我保证你没有足够的空间。
