python - 带模数的 Numpy 矩阵幂/指数？

Question

是否可以将 numpy 的 linalg.matrix_power 与模一起使用，以便元素不会增长到大于某个值？

Answer 1

为了防止溢出，您可以利用这样一个事实:如果您首先对每个输入数字取模，您会得到相同的结果；事实上:

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

对于矩阵 M。这来自以下两个基本恒等式，它们对整数 x 和 y(以及正幂 p)有效:

(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 中，您只需做

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

为了得到(arr**k) mod p。

如果这仍然不够(即，如果 [n mod p]**k 存在导致溢出的风险，尽管 n mod p 很小)，您可以将指数分解为多个指数。上面的基本身份产生

(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*... 或其任意组合。上面的恒等式允许您仅对小数进行小数取幂，这大大降低了整数溢出的风险。