Fibonacci modulo with Pisano period

Dealing with Fibonacci numbers becomes easily unmanageable for big numbers. However, if we are not interested to the full number, but just to its modulo, there is a handy trick that would help us.

The thing is that if we have a look at the Fibonacci sequence after applying to each element a modulo operator, we would notice that we always get periodic sequences.
Modulo 2 leads to a infinite repetition of three elements: 0, 1, 1
Modulo 3 to eight elements: 0, 1, 1, 2, 0, 2, 2, 1
Modulo 10 to sixty, et cetera.

There is no known way to get the length period given the modulo - called Pisano period - but we know that each Pisano period starts with "0, 1" and this signature is found just at the beginning of a period.

On this fact, the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, week 2, proposes three problems. I strongly suggest you to take the course before going on reading this post, getting back here to compare your solution with mine.

Here is the first one, Calculate Fibonacci modulo m.

Given two integers 𝑛 and 𝑚, output 𝐹𝑛 mod 𝑚.

The issue is that n could be up to 10^18. Less preoccupying the upper limit for m, fixed in 10^5.

A first naive solution would consist in calculating the required Fibonacci number, applying the modulo operator to it, return the result. Easy-peasy. However my naive python implementation started to get too slow for mere values about 10^5.

To use the Pisano period we have firstly to get its length. The only reasonable way I could think of, was looking for the modulo sequence checking for first repetition of the starting signature "0, 1".

def pisano(modulo):
    previous = 1
    current = 1

    result = 1
    while not (previous == 0 and current == 1):  # 1
        buffer = (previous + current) % modulo  # 2
        previous = current
        current = buffer

        result += 1

    return result

1. Loop until the starting signature is found
2. Get the next Fibonacci-modulo number

Let's now write a function to get a Fibonacci-modulo number. We could use instead a plain Fibonacci function and then apply the modulo operator to its result. This custom function saves the cost of adding big numbers between them.

def fibonacci(number, modulo):
    if number < 2:
        return number

    results = [1, 1]
    for _ in range(number - 2):
        results.append((results[-1] + results[-2]) % modulo)

    return results[-1]

Now, the solution itself is almost trivial.

def solution(number, modulo):
    return fibonacci(number % pisano(modulo), modulo)

Full python code, for both the trivial and Pisano case, and test case on GitHub.