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.

$\endgroup$
  • 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 Oct 2 '10 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 Oct 2 '10 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 May 26 '12 at 15:56
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$.

$\endgroup$
  • $\begingroup$ Sorry for the late accept, I have been busy lately. Thank you all for the help! $\endgroup$ – user9734 Oct 4 '10 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 Nov 7 '10 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.