[isani]

Factoring into powers of 2 seems to me like an unnecessary complication. It's possible to calculate an arbitrary power in O(log N) time without memoization.

  def __get_matrix_power(self, M, p):
    if p == 1:
      return M
    if p % 2 == 1: # odd power
      return self.__multiply_matrices(M, self.__get_matrix_power(M, p - 1))
    else: # even power
      K = self.__get_matrix_power(M, int(p/2))
      return self.__multiply_matrices(K, K)

[nabb]

Also working on pairs of consecutive fibonacci numbers (f_n, f_(n+1)) instead of the matrix [[f_(n+1) f_n] [f_n f_(n-1)]] makes this much simpler.

  def fib(n):
    def fib2(n):
      # returns (f_n, f_(n+1))
      if n == 0:
        return 0, 1
      if n % 2:
        a, b = fib2(n-1)
        return b, a+b
      a, b = fib2(n//2)
      return b*a + a*(b-a), a*a + b*b
    return fib2(n)[0]