Let's suppose that you've implemented the suggestion made by vnp, so that the line now reads:

nextFibonacci = (fibonacciNumbers[i - 1] + fibonacciNumbers[i]) % m

Could there still be an improvement? The Pisano period modulo \$m\$ is at most \$6m\$ and so the period-finding approach takes \$O(m)\$ steps, each of which involves the addition of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O(m\log m)\$.

There is an alternative approach, which is to compute the \$n\$th Fibonacci number modulo \$m\$ using the recurrence $$ \eqalign{F_{2n−1} &= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &= (2F_{n−1} + F_{n}) F_{n}}. $$ This can be implemented efficiently using recursion and memoization, for example you could use the @functools.lru_cache decorator, like this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_modulo(n, m):
    """Return the nth Fibonacci number modulo m."""
    if n <= 1:
        return n
    elif n % 2:
        a = fibonacci_modulo(n // 2, m)
        b = fibonacci_modulo(n // 2 + 1, m)
        return (a * a + b * b) % m
    else:
        a = fibonacci_modulo(n // 2 - 1, m)
        b = fibonacci_modulo(n // 2, m)
        return (2 * a + b) * b % m

This takes \$O((\log n)^2)\$ multiplications of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O((\log n \log m)^2)\$. So this approach would be an improvement on period-finding in cases where $$(\log n)^2\log m ≪ m.$$ For example, in the case \$n=10^{17}-1, m=10^5\$ given in the question, we have \$(\log n)^2\log m \approx 6000\$ and on this test case fibonacci_modulo is much faster than get_fibonacci_huge:

>>> n = 10**17 - 1
>>> m = 10**5
>>> timeit(lambda:get_fibonacci_huge(n, m), number=1)
0.09250206896103919
>>> fibonacci_modulo.cache_clear()
>>> timeit(lambda:fibonacci_modulo(n, m), number=1)
0.0001637069508433342

(Note the use of cache_clear to ensure that we have an empty cache and so the timing comparison is fair.)

Let's suppose that you've implemented the suggestion made by vnp, so that the line now reads:

nextFibonacci = (fibonacciNumbers[i - 1] + fibonacciNumbers[i]) % m

Could there still be an improvement? The Pisano period modulo \$m\$ is at most \$6m\$ and so the period-finding approach takes \$O(m)\$ steps, each of which involves the addition of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O(m\log m)\$.

There is an alternative approach, which is to compute the \$n\$th Fibonacci number modulo \$m\$ using the recurrence $$ \eqalign{F_{2n−1} &= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &= (2F_{n−1} + F_{n}) F_{n}}. $$ This can be implemented efficiently using recursion and memoization, for example you could use the @functools.lru_cache decorator, like this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_modulo(n, m):
    """Return the nth Fibonacci number modulo m."""
    if n <= 1:
        return n % m
    elif n % 2:
        a = fibonacci_modulo(n // 2, m)
        b = fibonacci_modulo(n // 2 + 1, m)
        return (a * a + b * b) % m
    else:
        a = fibonacci_modulo(n // 2 - 1, m)
        b = fibonacci_modulo(n // 2, m)
        return (2 * a + b) * b % m

This takes \$O((\log n)^2)\$ multiplications of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O((\log n \log m)^2)\$. So this approach would be an improvement on period-finding in cases where $$(\log n)^2\log m ≪ m.$$ For example, in the case \$n=10^{17}-1, m=10^5\$ given in the question, we have \$(\log n)^2\log m \approx 6000\$ and on this test case fibonacci_modulo is much faster than get_fibonacci_huge:

>>> n = 10**17 - 1
>>> m = 10**5
>>> timeit(lambda:get_fibonacci_huge(n, m), number=1)
0.09250206896103919
>>> fibonacci_modulo.cache_clear()
>>> timeit(lambda:fibonacci_modulo(n, m), number=1)
0.0001637069508433342

(Note the use of cache_clear to ensure that we have an empty cache and so the timing comparison is fair.)

Let's suppose that you've implemented the suggestion made by vnp, so that the line now reads:

nextFibonacci = (fibonacciNumbers[i - 1] + fibonacciNumbers[i]) % m

Could there still be an improvement? The Pisano period modulo \$m\$ is at most \$6m\$ and so the period-finding approach takes \$O(m)\$ steps, each of which involves the addition of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O(m\log m)\$.

There is an alternative approach, which is to compute the \$n\$th Fibonacci number modulo \$m\$ using the recurrence $$ \eqalign{F_{2n−1} &= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &= (2F_{n−1} + F_{n}) F_{n}}. $$ This can be implemented efficiently using recursion and memoization, for example you could use the @functools.lru_cache decorator, like this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_modulo(n, m):
    """Return the nth Fibonacci number modulo m."""
    if n <= 1:
        return n
    elif n % 2:
        a = fibonacci_modulo(n // 2, m)
        b = fibonacci_modulo(n // 2 + 1, m)
        return (a * a + b * b) % m
    else:
        a = fibonacci_modulo(n // 2 - 1, m)
        b = fibonacci_modulo(n // 2, m)
        return (2 * a + b) * b % m

This takes \$O((\log n)^2)\$ multiplications of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O((\log n \log m)^2)\$. So this approach would be an improvement on period-finding in cases where $$(\log n)^2\log m ≪ m.$$ For example, in the case \$n=10^{17}-1, m=10^5\$ given in the question, we have \$(\log n)^2\log m \approx 6000\$ which is a similar order of magnitude to \$m\$ and so the two functions have similar runtime:

>>> n = 10**17 - 1
>>> m = 10**5
>>> timeit(lambda:get_fibonacci_huge(n, m), number=1)
0.00015264307148754597
>>> fibonacci_modulo.cache_clear()
>>> timeit(lambda:fibonacci_modulo(n, m), number=1)
0.0001637069508433342

(Note the use of cache_clear to ensure that we have an empty cache and so the timing comparison is fair.) But with a larger value of \$m\$, fibonacci_modulo is thousands of times faster:

>>> m = 10**6
>>> timeit(lambda:get_fibonacci_huge(n, m), number=1)
0.9014073628932238
>>> fibonacci_modulo.cache_clear()
>>> timeit(lambda:fibonacci_modulo(n, m), number=1)
0.00017471308819949627

Let's suppose that you've implemented the suggestion made by vnp, so that the line now reads:

nextFibonacci = (fibonacciNumbers[i - 1] + fibonacciNumbers[i]) % m

Could there still be an improvement? The Pisano period modulo \$m\$ is at most \$6m\$ and so the period-finding approach takes \$O(m)\$ steps, each of which involves the addition of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O(m\log m)\$.

There is an alternative approach, which is to compute the \$n\$th Fibonacci number modulo \$m\$ using the recurrence $$ \eqalign{F_{2n−1} &= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &= (2F_{n−1} + F_{n}) F_{n}}. $$ This can be implemented efficiently using recursion and memoization, for example you could use the @functools.lru_cache decorator, like this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_modulo(n, m):
    """Return the nth Fibonacci number modulo m."""
    if n <= 1:
        return n
    elif n % 2:
        a = fibonacci_modulo(n // 2, m)
        b = fibonacci_modulo(n // 2 + 1, m)
        return (a * a + b * b) % m
    else:
        a = fibonacci_modulo(n // 2 - 1, m)
        b = fibonacci_modulo(n // 2, m)
        return (2 * a + b) * b % m

This takes \$O((\log n)^2)\$ multiplications of numbers with \$O(\log m)\$ digits, for an overall runtime of \$O((\log n \log m)^2)\$. So this approach would be an improvement on period-finding in cases where $$(\log n)^2\log m ≪ m.$$ For example, in the case \$n=10^{17}-1, m=10^5\$ given in the question, we have \$(\log n)^2\log m \approx 6000\$ and on this test case fibonacci_modulo is much faster than get_fibonacci_huge:

>>> n = 10**17 - 1
>>> m = 10**5
>>> timeit(lambda:get_fibonacci_huge(n, m), number=1)
0.09250206896103919
>>> fibonacci_modulo.cache_clear()
>>> timeit(lambda:fibonacci_modulo(n, m), number=1)
0.0001637069508433342

(Note the use of cache_clear to ensure that we have an empty cache and so the timing comparison is fair.)