Well, you can almost certainly use integer and modular arithmetic, with the Chinese remainder theorem, because the sequence is periodic for any modulus n you want. This requires some pre-computation, but probably you can predict how much in advance if you know how large a Fibonacci number ahead of time.
For example, I know the index for 34 must be a multiple of 3, just because 34 is even.