A few (perhaps naive) questions

[dlesnoff]

Apart from using an arbitrary precision integer arithmetic library, you can use 
the Chinese remainder theorem. Select a few (e.g. two) large integers that are 
pairwise coprime (they are if the integers are distinct primes). You can 
compute the sequence term by term modulo these primes separately. If you take 
the nth-term of each of these sequences, you can reconstruct the nth-term of 
the integer Fibonacci sequence by solving the modular system, given that the 
product of the integers is larger than the resulting sequence term.