मॉड्यूल के साथ बेवकूफ मैट्रिक्स पावर/एक्सपोनेंट?

Question

क्या यह modpyo के साथ numpy's linalg.matrix_power का उपयोग करना संभव है ताकि तत्व किसी निश्चित मान से बड़े न हों?

Answer 1

अतिप्रवाह को रोकने के लिए आदेश, आप तथ्य यह है कि आप एक ही परिणाम प्राप्त करता है, तो आप पहली बार अपने इनपुट संख्या में से प्रत्येक के सापेक्ष ले उपयोग कर सकते हैं; वास्तव में:

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

एक मैट्रिक्स M के लिए

। यह निम्न दो मौलिक पहचान है, जो पूर्णांकों x और 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* 

ही पहचान के साथ-साथ मैट्रिक्स के लिए पकड़, के बाद से मैट्रिक्स इसके अलावा और गुणा अदिश अलावा और गुणा के माध्यम से व्यक्त किया जा सकता। इसके साथ, आप केवल छोटी संख्याओं का विस्तार करते हैं (एन मॉड पी आम तौर पर एन से बहुत छोटा होता है) और अतिप्रवाह होने की संभावना कम होती है। NumPy में, आप इसलिए बस

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

आदेश (arr**k) mod p प्राप्त करने के लिए करना होगा।

यदि इससे भी पर्याप्त नहीं है (यानी, अगर वहाँ एक जोखिम है कि [n mod p]**kn mod p छोटे होने के बावजूद अतिप्रवाह का कारण बनता है), तो आप घातांक कई exponentiations में टूट सकता है। उपज ऊपर

(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. 

इस प्रकार मौलिक पहचान, आप a+b+… या a*b*… या किसी संयोजन के रूप में सत्ता k को तोड़ सकता है। उपरोक्त पहचानें आपको छोटी संख्याओं से छोटी संख्याओं के केवल एक्सपोनेंटियंस करने की अनुमति देती हैं, जो पूर्णांक अतिप्रवाहों के जोखिम को बहुत कम करती है।

Answer 2

स्पष्ट दृष्टिकोण के साथ क्या गलत है?

उदा।

import numpy as np 

x = np.arange(100).reshape(10,10) 
y = np.linalg.matrix_power(x, 2) % 50 

Answer 3

Numpy से कार्यान्वयन का उपयोग करना:

https://github.com/numpy/numpy/blob/master/numpy/matrixlib/defmatrix.py#L98

मैं इसे एक सापेक्ष शब्द जोड़कर अनुकूलित। हाउवर, वहां एक बग है, यदि एक ओवरफ्लो होता है, तो OverflowError या किसी अन्य प्रकार का अपवाद उठाया नहीं जाता है। उस बिंदु से, समाधान गलत होगा। एक बग रिपोर्ट here है।

यहां कोड है। देखभाल के साथ प्रयोग करें:

from numpy.core.numeric import concatenate, isscalar, binary_repr, identity, asanyarray, dot 
from numpy.core.numerictypes import issubdtype  
def matrix_power(M, n, mod_val): 
    # Implementation shadows numpy's matrix_power, but with modulo included 
    M = asanyarray(M) 
    if len(M.shape) != 2 or M.shape[0] != M.shape[1]: 
     raise ValueError("input must be a square array") 
    if not issubdtype(type(n), int): 
     raise TypeError("exponent must be an integer") 

    from numpy.linalg import inv 

    if n==0: 
     M = M.copy() 
     M[:] = identity(M.shape[0]) 
     return M 
    elif n<0: 
     M = inv(M) 
     n *= -1 

    result = M % mod_val 
    if n <= 3: 
     for _ in range(n-1): 
      result = dot(result, M) % mod_val 
     return result 

    # binary decompositon to reduce the number of matrix 
    # multiplications for n > 3 
    beta = binary_repr(n) 
    Z, q, t = M, 0, len(beta) 
    while beta[t-q-1] == '0': 
     Z = dot(Z, Z) % mod_val 
     q += 1 
    result = Z 
    for k in range(q+1, t): 
     Z = dot(Z, Z) % mod_val 
     if beta[t-k-1] == '1': 
      result = dot(result, Z) % mod_val 
    return result % mod_val