Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
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 –  Gerhard Paseman Oct 2 '10 at 6:11
2  
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. –  Somnath Basu Oct 2 '10 at 6:19
    
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. –  Jyrki Lahtonen May 26 '12 at 15:56

2 Answers 2

up vote 10 down vote accepted

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$.

share|improve this answer
    
Sorry for the late accept, I have been busy lately. Thank you all for the help! –  user9734 Oct 4 '10 at 12:28
    
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$. –  Nick S Nov 7 '10 at 19:52

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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