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.
Edit: In practical terms perhaps you just sieve on a range on integers instead of using the Chinese remainder theorem (see comments)? Using the number of bits of input as the complexity measure N, you'd need a range of length proportional to N (take some easy rational upper and lower bounds to log 2/log (golden ratio)). Then looking mod 2 you can strike out at least one third of the numbers. Modulo other small primes you strike out some proportion which depends on case but is not too small. You are going to continue until only one integer from the range remains as a candidate. This really doesn't look too bad: the period mod p may be large or small, but what matter matters is the proportion of the time a given residue class appears.