10
$\begingroup$

I'm trying to write a program with an input of numbers $n$ and $k$ (where $n<10^{1000}$ and $k<10^9$), where I compute fib[n] % k. What is a good FAST way of computing this?

I realize that the resulting series is periodic, just not sure how to find it efficiently.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ If k has no large prime or large prime power factors, then brute force combined with the Chinese Remainder Theorem will get you somewhere quickly. Otherwise use recursions to do the Fibonacci series mod k, to compute e.g. F(2j) and F(2j+1) mod k from F(j) and f(j+1) mod k. If n and k satisfy the bounds you say, a reasonably coded laptop can give you the answer in seconds or less. Gerhard "Ask Me About System Design" Paseman, 2010.10.01 $\endgroup$
    – Gerhard Paseman
    Commented Oct 2, 2010 at 6:11
  • 2
    $\begingroup$ The Fibonacci entry in wikipedia has this identity : $F_{lk+c} = \sum_{i=0}^l {l\choose i} F_{c-i} F_k^i F_{k+1}^{l-i}$. It definitely seems to be relevant in your case, where write $n=lk+c$ and then you have to know $F_j$ mod $k$ for $j=1,\ldots,k+1$ as well as ${l\choose i}$ mod $k$. I don't know if this is efficient enough. $\endgroup$
    – Somnath Basu
    Commented Oct 2, 2010 at 6:19
  • $\begingroup$ Modulo a prime $>5$ the Fibonacci sequence has a period that is either a factor of $p-1$ or $2(p+1)$. This follows from Binet's formula. If $5$ is a quadratic residue modulo $p$, then $$x^2=x+1$$ has two roots in the field $F_p$, and thus both roots have multiplicative orders that are factors of $p-1$. OTOH if $5$ is a quadratic non-residue, then the roots $\tau_1,\tau_2$ of that polynomial are in the finite field $K=F_{p^2}$. But by known Galois theory of $K$ we then have $$\tau_1^p=\tau_2=-1\frac1{\tau_1},$$ so $\tau_^{p+1}=\tau_2^{p+1}=-1.$$ See math.stackexchange.com/a/150062/11619. $\endgroup$
    – Jyrki Lahtonen
    Commented May 26, 2012 at 15:56

2 Answers 2

Reset to default
15
$\begingroup$

This is really just an expansion of Gerhard's comment. One has the matrix formula $$\begin{pmatrix} 1&1\\\ 1&0 \end{pmatrix}^n= \begin{pmatrix} F_{n+1}&F_n\\\ F_n&F_{n-1} \end{pmatrix} $$ so the problem reduces to computing $A^n$ modulo $k$ where $$A=\begin{pmatrix} 1&1\\\ 1&0 \end{pmatrix}.$$ This can be done by the repeated squaring method often used in modular exponentiation. The idea is to compute $A^n$ recursively either as $(A^m)^2$ or $A(A^m)^2$ according to whether $n=2m$ or $n=2m+1$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry for the late accept, I have been busy lately. Thank you all for the help! $\endgroup$
    – user9734
    Commented Oct 4, 2010 at 12:28
  • $\begingroup$ Also note that the order of $GL_2(\Z_k)$ is much smaller than $n$, and the order of the matrix divides this order. If $l$ is the reminder of $n$ divided by this order, then $A^n=A^l \mod p$. Last but not least it is enough to consider the subgroup of matrices of $det =\pm1$. $\endgroup$
    – Nick S
    Commented Nov 7, 2010 at 19:52
3
$\begingroup$

Perhaps Elsenhans, Jahnel, "The Fibonacci sequence modulo $p^2$ – An investigation by computer for $p < 10^{14}$" http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf will be interesting for you. There are sections about the algorithm.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .