模数乘方矩阵幂/指数? [英] Numpy matrix power/exponent with modulo?

问题描述

是否可以对numpy的linalg.matrix_power进行模运算，以使元素的大小不超过特定值?

Is it possible to use numpy's linalg.matrix_power with a modulo so the elements don't grow larger than a certain value?

推荐答案

为了防止溢出，您可以使用以下事实:如果您首先对每个输入数字取模，则会得到相同的结果.实际上:

In order to prevent overflow, you can use the fact that you get the same result if you first take the modulo of each of your input numbers; in fact:

(M**k) mod p = ([M mod p]**k) mod p,

表示矩阵 M.这来自以下两个基本标识，它们对于整数x和y有效:

for a matrix M. This comes from the following two fundamental identities, which are valid for integers x and y:

(x+y) mod p = ([x mod p]+[y mod p]) mod p  # All additions can be done on numbers *modulo p*
(x*y) mod p = ([x mod p]*[y mod p]) mod p  # All multiplications can be done on numbers *modulo p*

由于矩阵加法和乘法可以通过标量加法和乘法来表示，因此矩阵也具有相同的标识.这样，您只需要对较小的数字求幂(n mod p通常比n小得多)，并且不太可能发生溢出.因此，在NumPy中，您只需

The same identities hold for matrices as well, since matrix addition and multiplication can be expressed through scalar addition and multiplication. With this, you only exponentiate small numbers (n mod p is generally much smaller than n) and are much less likely to get overflows. In NumPy, you would therefore simply do

((arr % p)**k) % p

以获取(arr**k) mod p.

如果这还不够(即，尽管n mod p很小，即使[n mod p]**k仍可能导致溢出)，则可以将幂分解成多个幂.高于产量的基本身份

If this is still not enough (i.e., if there is a risk that [n mod p]**k causes overflow despite n mod p being small), you can break up the exponentiation into multiple exponentiations. The fundamental identities above yield

(n**[a+b]) mod p = ([{n mod p}**a mod p] * [{n mod p}**b mod p]) mod p

和

(n**[a*b]) mod p = ([n mod p]**a mod p)**b mod p.

因此，您可以将电源k分解为a+b+…或a*b*…或它们的任意组合.上面的身份仅允许您对小数进行小数乘幂运算，从而大大降低了整数溢出的风险.

Thus, you can break up power k as a+b+… or a*b*… or any combination thereof. The identities above allow you to perform only exponentiations of small numbers by small numbers, which greatly lowers the risk of integer overflows.

这篇关于模数乘方矩阵幂/指数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！