Advertisement
HellFinger

Untitled

Oct 20th, 2019
209
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def multiply_by_mod(matrix1, matrix2, mod):
  2.     matrix = [[0,0],[0,0]]
  3.     matrix[0][0] = (matrix1[0][0] * matrix2[0][0] + matrix1[0][1] * matrix2[1][0]) % mod
  4.     matrix[0][1] = (matrix1[0][0] * matrix2[0][1] + matrix1[0][1] * matrix2[1][1]) % mod
  5.     matrix[1][0] = (matrix1[1][0] * matrix2[0][0] + matrix1[1][1] * matrix2[1][0]) % mod
  6.     matrix[1][1] = (matrix1[1][0] * matrix2[0][1] + matrix1[1][1] * matrix2[1][1]) % mod
  7.  
  8.     return matrix
  9.  
  10.  
  11. def fast_pwr(matrix, deg, mod):
  12.     if deg == 1 or deg == 0:
  13.         return matrix
  14.  
  15.     if deg % 2 == 0:
  16.         f = fast_pwr(matrix, deg/2, mod)
  17.         return multiply_by_mod(f, f, mod)
  18.     if deg % 2 == 1:
  19.         f = fast_pwr(matrix, (deg - 1), mod)
  20.         return multiply_by_mod(f, matrix, mod)
Advertisement
RAW Paste Data Copied
Advertisement