Function modular_exponentiation

maths/matrix_exponentiation.py:31–38

(a: Matrix, b: int)

def modular_exponentiation(a: Matrix, b: int) -> Matrix:
    matrix = Matrix([[1, 0], [0, 1]])
    while b > 0:
        if b & 1:
            matrix *= a
        a *= a
        b >>= 1
    return matrix


def fibonacci_with_matrix_exponentiation(n: int, f1: int, f2: int) -> int: